Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
Time limit = 5 second(s)
Rectangular casket lid is decorated with jewels. All jewel positions has integer coordinates (0 ≤ X,Y ≤ 100). No two jewels are placed to the same place. Jewels form axially symmetry (two axes of symmetry are parallel to sides) picture. But some jewels were lost. The problem is to change positions of minimal number of jewels and make picture axially symmetric.There may be several solutions, output one of them.
Input The first line contains two even numbers --- lengths of sides of rectangular casket lid. The next line has the number N of jewels and N lines describing jewels positions follow. Each line contains three numbers: jewel id, X and Y jewel's coordinates. Jewels ids are the numbers 1, 2, ... N.
See the figure below: casket with some jewels lost (left) and casket with moved 3-rd and 4-th jewels to their new positions so that picture is axially symmetric (right).
For this figure input data is
6 4 5 1 1 3 2 1 1 3 4 3 4 4 2 5 5 3
Output The first line should contain minimal number M of jewels to move. Next M lines should have the form:
< jewel id > < new X coordinate > < new Y coordinate >
For the casket in the figure above output may be the following:
2 4 5 1 3 3 2
Input#14 12 8 1 1 2 2 3 2 3 1 8 4 1 9 5 1 10 6 3 8 7 3 9 8 3 10 |
Output#12 4 1 3 6 3 3 |
Author:
Moscow region school contest, 8-9 January 2003
28 January 2003
© acm.mipt DevGroup The page was generated in 190ms |