ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC, Eastern subregion, Yekaterinburg, October 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Domino Recognition

Time limit: 1.0 second
Memory limit: 64 MB
In Vovan's casino, all croupiers are robots. Once a thought occurred to Vovan that it would be useful if robots that play dominoes with clients could recognize the type of a bone before it is turned over, that is, when a bone lies on a table with its face down. Fortunately, it is possible since the dots on bones are diamonds, and diamonds can be seen in X-rays. Moving a manipulator over a bone, a robot can direct X-rays through it to a camera located in the robot's leg. Using the obtained photo, a special program must recognize the type of the bone. Now try to guess who will write this program.
A bone is a rectangle of size L × 2L (1 ≤ L ≤ 100) composed of two squares. In each of the squares, there are from 0 to 6 dots arranged in the classical way. In order to describe the arrangements of dots on a square, we consider a smaller square with the same center whose sides are twice shorter than the sides of the bigger square and parallel to them.
1 dot is put at the center of the square
2 dots are situated at the lower left and upper right corners of the smaller square (we assume that a bone is oriented vertically)
3 dots are arranged in the same way as 2 dots plus a dot at the center of the square
4 dots are at the four corners of the smaller square
5 dots are arranged in the same way as 4 dots plus a dot at the center of the square
6 dots: four dots are put at the corners of the smaller square and two dots are at the middles of the sides of the smaller square that are parallel to the long sides of the bone.
Your task is to analyze a photo of a bone. It is known that the photo shows all dots of exactly one bone. The plane of the camera's receiver is parallel to the table's surface; there are no perspective or other distortions, but the bone may be arbitrarily rotated in the plane of the table. Don't forget that the bone on the table is turned over.


The first line contains the number of dots seen in the photo N (1 ≤ N ≤ 12). The next N lines contain the coordinates of these dots. The coordinates are accurate to 0.0001. Absolute values of coordinates do not exceed 2000. The photo shows the real size of the bone.


Output integers A and B (AB), which are the numbers of dots in the two squares of the bone. If several answers are possible, they should be given in the lexicographical order. It is guaranteed that the input is correct.


1.12 2.2
7 -3.0001
0 2
1 1
Problem Author: Ekaterina Ovechkina, Stanislav Vasilyev
Problem Source: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
To submit the solution for this problem go to the Problem set: 1509. Domino Recognition