IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
822 . 搶救果凍大作戰
TopCoder
Description
卓利教練是$N$個孩子（編號為$1\sim N$）的足球教練。每天訓練結束後，卓利教練都會將$N$包零食灑在足球場上，當作給努力練球之後的孩子們當作獎勵。
然而，練完球的孩子們早已筋疲力竭。這使得他們在輪到自己拿零食時，只願意去拿距離（歐幾里得距離，就是你最常見的那種）自己最近的零食。但這樣小孩子有可能會打架---假設某一包零食對所有的孩子來說都是最近的，那麼這$N$個小孩就會集體衝過去並打成一片。卓利教練作為資深的足球教練，早就預判了這個潛在的問題並也有一套解決這個問題的方法：他會一個一個地叫孩子去拿自己的零食；如此一來，孩子們就不會打成一片了。而學生們對教練也很有禮貌，如果輪到某個孩子拿零食時，發現多包零食與自己的距離相同，那麼他會詢問教練在這些距離自己最近的零食中，要拿哪一包比較好。
教球三十年以來，教練都是這麼做的。但今天發生了一點意外！今天教練灑零食的時候，他不小心把自己要吃的藍莓果凍一起灑出去了！藍莓果凍是教練最心愛的點心，這是他心心念念晚上回家時要吃的甜點。於是此時，足球場上便有$N$個小孩和$N + 1$份零食（編號$1 \sim N + 1$）。教練很緊張，他思索著是否有一種叫小孩去拿零食的順序，能在$N$名小孩都各自拿完一包零食後，自己的藍莓果凍還留在場上因而保住自己最心愛的果凍？
Input Format
每份測試檔案的第一行都會包含恰一個整數$T$，代表這份檔案內含$T$筆測試資料。
每份測試資料的第一行會有一個正整數$N$，代表小孩子們的數量。
接下來的$N$行是小孩子們的位置，其中的第$i$行包含兩個整數$X_i, Y_i$，代表$N$個小孩在足球場上的座標位置。
接下來的$N + 1$行是零食（1號零食是卓利教練最愛的藍莓果凍）們的位置，其中的第$j$行包含兩個整數$X_j, Y_j$，代表第$j$號零食在足球場上的座標位置。
- $1 \leq T \leq 100$
- $-10^ 9 \leq X_i, Y_i, X_j, Y_j \leq 10^ 9$
- $1 \le N \le 10$
Output Format
對於每筆測試資料，第一行請輸出型如Case #x: y的字串，其中$x$是這是第幾筆測資的編號（第一筆測資的$x = 1$），而
* 如果卓利教練的果凍沒救了（找不到任何一種叫小孩子拿零食的順序可以保住他的果凍），則$y = \texttt{IMPOSSIBLE}$。
* 反之，$y = \texttt{POSSIBLE}$。
如果卓利教練有辦法保住他的果凍，請告訴他該用什麼順序叫孩子去拿零食以及每個人應該拿哪一包零食。更具體地說，請額外輸出$N$行，其中第$i$行包含兩個以空白分隔的整數$A_i, B_i$，代表教練應該在第$i$次呼叫孩子的時候應該呼叫編號為$A_i$的孩子，並指示他去拿$B_i$號零食。特別需要注意的是，$B_i$號零食必須要是足球場上仍未被取走的零食中，其中一個距離$A_i$號孩子最近的零食。
Sample Input 1
2
-3 0
-1 0
3 0
-2 -1
-2 1
1
0 0
1 1
2 2
3
10 0
-10 0
0 0
0 5
-1 0
5 0
0 -5
2
3 4
3 4
5 7
3 4
5 7
Sample Output 1
1 2
2 3
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
1 3
2 2
3 4
Case #4: POSSIBLE
1 2
2 3
Hints
Problem Source
Google Code Jam 2022 Round 2: Saving the Jelly - Test Set 1
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~2 | 無額外限制 | 100 |