Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
凸包的严格凸多边形
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 43, Accepted users: 38
Problem 11326 : No special judgement
Problem description
  凸包(convex hull),对于给定集合X,所有包含X的凸集的交集称为X的凸包,记作con(X)。
对于ACMer来说,这么严格复杂的定义可能是没有必要的。我们只要知道平面有限点集的凸包是一个凸多边形就行了。
现在的问题是给定一个平面点集,求出其“严格凸多边形”的凸包。“严格”的意思是凸多边形的边上没有任意三点共线。

Input
  输入有多个案例。每个案例的第一行是一个整数n,n≤100。随后n行,每一行有2个整数,表示点的x、y坐标,0≤x、y≤2147483647。一个单独的0表示输入结束。没有任何点的坐标是完全一样的。

Output
  对每一个案例,首先输出一行为其端点的个数,然后按逆时针输出其凸包的顶点的坐标。输出起点是所有顶点的最下最左点(首先是最下,如果有多个点同样处于最下,则取最靠左的)。每个顶点输出一行,中间用空格隔开。

Sample Input
3
0 0
100 100
100 0
0
Sample Output
3
0 0
100 0
100 100
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2012 today,16258739 total, since 2010-05-07