IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
881 . 整理桌面
TopCoder
Tags
Description
你是否有不小心放太多文件在電腦桌面，導致桌面凌亂不堪的經驗呢？習慣將環境整理乾淨的人們可能沒有，但 8e7 就不是這樣的人。這天，8e7 發現他的電腦桌面實在是太過凌亂，其中一項很大的原因就是因爲他留了太多沒有用的文件在桌面上當作暫存，只要將這些文件刪除，桌面勢必可以乾淨不少。
但 8e7 不習慣將環境整理乾淨的原因終究還是因為懶惰，因此，他希望能花最少的力氣來刪除這些文件。8e7 發現，他只要在桌面上選取一個方框，就可以將方框內的文件都變成選取狀態，只要點選刪除，就可以一口氣把選取狀態中的文件全數刪除，不過當他選取第二個方框後就發現事情並沒有那麼單純！
實際上，8e7 電腦的作業系統是這樣設計的：每當 8e7 在桌面上選取一個方框後，所有在方框內的文件的選取狀態都會反轉。
什麼意思呢？也就是說，只要在方框內的文件原本是未選取狀態，這份文件就會變成選取狀態；而如果這份文件本來就已經是選取狀態，則他會變回未選取狀態！
這樣的操作變得稍顯複雜許多，但 8e7 仍然不想放棄使用最少的力氣來選取所有的文件好讓他一鍵刪除它們。現在，8e7 已經將所有的文件轉換成 2D 平面上的 $N$ 個座標，其中有 $M$ 個文件是需要被刪除的，請你撰寫一支程式，在讀入所有文件的座標後，給 8e7 一組使用最少次方框選取操作框出所有文件的方法。
Input Format
輸入首行有兩個正整數 $N, M$，代表 8e7 電腦桌面總共的文件數和在其中需要被刪除的文件數。
接下來 $N$ 行，第 $i$ 行兩個整數 $x_i, y_i$，代表第 $i$ 個文件的座標。其中第 $1\sim M$ 個文件為 8e7 希望刪除的文件。
- $1\leq M \leq N\leq 14$
- $-10^ 9 \leq x_i, y_i\leq 10^ 9$
- 保證所有文件的座標兩兩相異
Output Format
首行輸出一個正整數 $k$，代表你需要使用的方框選取操作數量。
接下來 $k$ 行，第 $j$ 行要有四個整數 $l_j, d_j, r_j, u_j$，代表你第 $j$ 次要選取的方框為座標 $(l_j, d_j)$ 和 $(r_j, u_j)$ 形成的矩形，必須滿足 $-2\times 10^ 9\leq l_j\leq r_j\leq 2\times 10^ 9$ 且 $-2\times 10^ 9\leq d_j\leq u_j\leq 2\times 10^ 9$。代表對於第 $i$ 個文件，若文件 $i$ 滿足 $l_j\leq x_i\leq r_j$ 且 $d_j\leq y_i\leq u_j$ 的話，他的選取狀態就會被反轉。
你輸出的選取方法必須恰讓第 $1\sim M$ 個文件在選取狀態、其餘的文件則需要在未選取狀態。若有多組可能的解答，輸出任何一種皆會被視為正確。
Sample Input 1
1 4
2 2
5 4
3 3
4 5
Sample Output 1
1 2 5 5
3 3 4 5
Sample Input 2
-3 5
-3 9
6 0
6 5
-3 8
6 2
Sample Output 2
-3 0 6 0
-3 9 -3 9
-3 0 -3 5
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~11 | 無額外限制 | 100 |