Problem A: MC part deux
The Dean has determined that mathies have outgrown the building that
has served them so well for many years. Luckily for him, the PM has
decided to stimulate the economy by funding a new math building. To
maximize the stimulating effect, the construction process is outsourced
to a software engineering consultant who employs agile methodologies.
The building will be built first, and designed later. The Dean has some
concerns about this innovative process. After all, it would be very
embarrassing if the walls of the new math building failed to line up at
right angles!
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 Specification
Input consists of a number of test cases.
The first line of each test case 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 -1000000 and
no greater than 1000000.
Each of the following lines contains exactly six integers a,
b, c, x, y, z. The integers a,
b, and c are the numbers of three 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 T1, T2, ..., Tn
such that two of the vertices of Ti are also vertices of Ti+1 for all 0<i<n,
a is a vertex of T1, and b is a vertex of Tn.
The last line of input is 0 0. These zeros are not values
of n and m, and should not be processed as such.
Sample Input
1 3
1 3 2 1 2 1
0 0
Output Specification
Output consists of exactly m lines for each test case.
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
Output for Sample Input
0 0
0 1
1 0
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.