[Solution] Saving the Jelly Solution Round 2 2022 - Code Jam 2022

[Solution] Saving the Jelly Solution Round 2 2022 - Code Jam 2022

Problem

Mr. Jolly teaches football (or soccer, for US speakers) to N$N$ children numbered from 1$1$ to N$N$. He has taken to leaving sweets on the field where the games take place, one for each child. After the game is finished, each child can grab and eat one sweet as their reward.

The children are tired after games, so each child wants to grab the sweet closest to them. This could lead to fights — if the same sweet is closest to two or more children. To avoid that, after the game all the children stop where they are, and Mr. Jolly calls out their names, one by one. When a child's name is

Solution Click Below:-  CLICK HERE

 called, they grab the closest sweet to them (out of the ones that weren't already grabbed, of course). In the case where two or more sweets are tied for the smallest distance, Mr. Jolly can decide which one the child grabs.

Spiraling Into Control Solution Round 2 2022

Pixelated Solution Circle Round 2 2022 

Saving the Jelly Solution Round 2 2022

I, O Bot Solution Round 2 2022 

This has worked very well for Mr. Jolly for a while now, but today disaster struck! While laying out the sweets, Mr. Jolly accidentally dropped his blueberry jelly that he planned to eat after all the children go home. So now there are N$N$ children on the field, and N+1$\mathbf{N}+1$ sweets. The sweets are numbered from 1$1$ to N$N$, with sweet 1$1$ being Mr. Jolly's blueberry jelly. Is there a way for Mr. Jolly to save his blueberry jelly by calling the children's names in such an order that the blueberry jelly is the one sweet left over?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. Each test begins with a line containing a single integer, N$N$, the number of children on the field. The next N$N$ lines describe the positions of the children. Each of these lines contains two integers, Xi${\mathbf{X}}_{\mathbf{i}}$ and Yi${\mathbf{Y}}_{\mathbf{i}}$, representing the position of the i$i$⁠-th child after the game ends. Then there are N+1$\mathbf{N}+1$ more lines that describe the positions of sweets after the game, where the first of the sweets is Mr. Jolly's blueberry jelly. Each of these lines contains two integers, Xj${\mathbf{X}}_{\mathbf{j}}$ and Yj${\mathbf{Y}}_{\mathbf{j}}$, representing the position of the j$j$⁠-th sweet.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is IMPOSSIBLE if there is no way Mr. Jolly can choose the children (and break ties for the closest sweet) to leave his blueberry jelly uneaten. Otherwise, if Mr. Jolly can save his blueberry jelly, y$y$ is POSSIBLE. If Mr. Jolly can save his jelly, output N$N$ additional lines representing the order the children will go and which jellies they will pick. The i$i$⁠-th line should contain two integers Ai$A_i$ and Bi$B_i$ representing that child Ai$A_i$ will go next and will pick sweet Bi$B_i$. The sweet Bi$B_i$ must be the closest (or tied for the closest) sweet to child Ai$A_i$ when they go to pick their sweet.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
−109≤Xi≤109$-{10}^9\le {\mathbf{X}}_{\mathbf{i}}\le {10}^9$, for all i$i$.
−109≤Yi≤109$-{10}^9\le {\mathbf{Y}}_{\mathbf{i}}\le {10}^9$, for all i$i$.
−109≤Xj≤109$-{10}^9\le {\mathbf{X}}_{\mathbf{j}}\le {10}^9$, for all j$j$.
−109≤Yj≤109$-{10}^9\le {\mathbf{Y}}_{\mathbf{j}}\le {10}^9$, for all j$j$.

Test Set 1 (Visible Verdict)

Time limit: 10 seconds.
1≤N≤10$1\le \mathbf{N}\le 10$.

Test Set 2 (Hidden Verdict)

Time limit: 45 seconds.
1≤N≤1000$1\le \mathbf{N}\le 1000$.