CS3233 Final "Endgame" Team Contest


2019-04-15 01:00 AKDT

CS3233 Final "Endgame" Team Contest


2019-04-15 05:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -733 days 11:07:06

Time elapsed


Time remaining


Problem J
Jus Accrescendi

“Say not you know another entirely, till you have divided an inheritance with him.” ­–Johann Lavater.

There has been a heated broil between the three children of the late prime minister over how to divide their father’s property. Reading the will, it is discovered that their father wanted the most wise of his children to inherit his fortunes.

The old man was a fan of triangles and hence wrote:

My property shall be vested into him who is able to plant exactly $T$ trees on my property, such that no two trees are planted at the same location, no three trees lie on a straight line, and the number of triangles with integer area, formed by choosing three trees as vertices, is exactly $B$.

The late prime minister was always a little eccentric and his will was no exception. The law is the law, however, and the will must be followed.

The land can be represented as a Cartesian plane, with his property representing all the points whose $x$- and $y$-coordinates do not exceed $1\, 000$ in absolute value. Due to archaic legal constraints, trees can only be planted at locations where both coordinates are integers.

\includegraphics[width=0.8\textwidth ]{jusacc.png}
Figure 1: Illustration of Sample Input 2.

You, the executor, have been commissioned by the high court of the land to solve this perplexing puzzle to demonstrate that a solution indeed exists; if not, the will will be rendered invalid.


The first and only line of input contains two integers $T$ ($3 \leq T \leq 500$) and $B$ ($1 \leq B \leq 3\cdot 10^7$), the number of trees to be planted and the required number of triangles with integer area.



  • $T$ lines, where the $i^\text {th}$ of these lines contains two integers, $x_ i$ and $y_ i$ ($-1\, 000 \leq x_ i, y_ i \leq 1\, 000$), describing the location of the $i^\text {th}$ tree, if a solution exists, or

  • a single line containing the string IMPOSSIBLE, otherwise.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
4 4
-1 -1
-1 1
1 -1
1 1
Sample Input 2 Sample Output 2
5 6
1 3
2 1
3 4
4 1
5 2
Sample Input 3 Sample Output 3
5 8