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

Bulgarian Contest September 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Squares

Time limit: 0.5 second
Memory limit: 64 MB
You are given n (1 ≤ n ≤ 50) squares and point P. The distance between P and square is the shortest line segment that connects P with the contour or the internal area of the square. If P is inside the square then the distance is zero. It is possible some squares to be points i.e. to have vertices that coincide. Write a program that will sort the squares in ascending order according the distance from P.


The first line contains the integer n. The following n lines contain four integers in the range (−9999, 9999). The first two numbers define the x and y coordinates of one of the vertices of the square, the next two numbers define the opposite vertex. The last line contains the x and y coordinates of P.


The output should be a line containing the ids of the squares sorted according to the distance from P. The ids are defined according to the order in which the squares are given in the input. Use ids to break ties i.e. if two squares are the same distance from P then write the square with the lowest id first. Using 10−14 precision when comparing the distances is accurate enough.


0 0 1 1
0 3 1 4
0 0
1 2
To submit the solution for this problem go to the Problem set: 1111. Squares