荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: Convex hull
发信站: 荔园晨风BBS站 (Sun Mar 28 11:47:11 2004), 站内信件

Convex hull
Time Limit: 1.0 second
Memory Limit: 1 000 КБ

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) 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.

Input
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.

Output
Your program should print the sequence of broken line’s vertexes.
Vertexes 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 in the file only once.

No three consecutive vertexes of broken line should lie on a straight line.


Sample Input
4
3 3
3 1
2 2
4 2

Sample Output
3 1
4 2
3 3
2 2


--
Long long ago,there is a hero stand at the edge of the land.......

     ▁▁
   ▕天外▏
   ▕飞仙▏
     ▔▔

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.157]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店