Problem D
MC Part Deux
The Dean sneaks out one night with a tape measure to survey the last remaining grassy area on campus, where the new building will go. He drives stakes into the ground, then measures the distances between them. Afterwards, he retreats into his office to construct a map from his measurements. He notices that the first three stakes form a right-angled triangle with arms of length one metre and hypotenuse of length $\sqrt {2}$ metres. And that’s not all. The Dean plots these first three stakes on a piece of graph paper at coordinates $(0,0)$, $(0,1)$, and $(1,0)$. After plotting some of the other stakes, it turns out that all of the stakes happen to be precisely at lattice points (i.e., points with integer coordinates) on the graph paper. Still, plotting all of the many stakes is tedious, so he asks his co-op student (i.e. you) to help out.
Input
The first line of input contains two integers $n$ and $m$, each at least $1$ and no larger than $1000$.
The integer $n$ is the number of lines that follow, and $m$ is the number of stakes. The stakes are numbered from $1$ to $m$. All of the stakes are at distinct locations. The $x$ and $y$ coordinates of each stake are no less than $-1\, 000\, 000$ and no greater than $1\, 000\, 000$.
Each of the following $n$ lines contains exactly six integers $a$, $b$, $c$, $x$, $y$, $z$. The integers $a$, $b$, and $c$ are the numbers of three distinct stakes. The three stakes are always listed in counter-clockwise order. That is, to move from stake $a$ to stake $b$ and then to stake $c$, one must turn left at stake $b$. The number $x$ is the square of the distance from stake $a$ to stake $b$. The number $y$ is the square of the distance from stake $b$ to stake $c$. The number $z$ is the square of the distance from stake $c$ to stake $a$.
Every stake will appear in at least one line of the input. For every pair of stakes $a$, $b$, there is a subset of the triangles in the input that forms a sequence $T_{1}, T_{2}, \ldots , T_{k}$ such that two of the vertices of $T_{i}$ are also vertices of $T_{i+1}$for all $1 \le i < k$, $a$ is a vertex of $T_{1}$, and $b$ is a vertex of $T_{n}$.
Output
Output consists of exactly $m$ lines. The $m$ lines describe the stakes $1$ to $m$ in sequence. Each line contains two integers, giving the $x$ and $y$ coordinates of the stake. The first three lines of output for each test case are always:
0 0 0 1 1 0
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 1 3 2 1 2 1 |
0 0 0 1 1 0 |
