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

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.

Input

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.

Output

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.

Sample

inputoutput
2
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