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

1305. Convex Hull

Time limit: 1.0 second
Memory limit: 64 MB
Let a finite set of points M be defined on plane. The plane has a usual Cartesian coordinates. Well-formed convex hull of set M is minimal (relative to inclusion) convex set, containing M, and bounded by closed broken line. All sections of this broken line should be parrallel to axes or inclined by 45°.
Your task is to find a well-formed convex hull for a given set M.


In the first line an number N (1<=N<=100 000) of following lines is written. In the second and all next lines coordinates of set’s points is written. In every line there are coordinates (two numbers separated several spaces, each number is greater or equal to 0 and less or equal to 1000) of only one point. Some points of set can overlap, thus the same coordinates can be found in different lines.


Your program should print the sequence of broken line’s vertices. Vertices should be enumretated in the counter clock-wise order. As a first vertex any of them can be taken. In every line exactly one vertex’s coordinates (two numbers, separated by spaces) should be put out. Every vertex of broken line should be mentioned only once.
No three consecutive vertices of broken line should lie on a straight line.


3 3
3 1
2 2
4 2
3 1
4 2
3 3
2 2
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998