同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21305_求凸包

2022-5-16 18:19| 发布者: Hocassian| 查看: 43| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505125585599-Problem List-采集的数据-后羿采集器.html

Pro.ID

21305

Title

求凸包

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21305

AC

Submit

157

Ratio

20.38%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

【计算几何基础题】

给定N个点的点集，求此点集的凸包。

输入

给出多个CASE，每个CASE的第一行是一个N（ 3 ≤ N ≤ 80000 ），表示此点集有N个点，然后会有N行，每行有两个整数 X_i Y_i(|X_i|, |Y_i| ≤ 210 )，用空格隔开，表示第i个点的坐标。当N=0时表示结束，并不处理此CASE。
保证凸包上不会出现三点共线

输出

Description

【计算几何基础题】

给定N个点的点集，求此点集的凸包。

Input

Output

对应输入的每个CASE，以凸包上纵坐标最小的点（若有多个则选横坐标最小的）做为开始点，按逆时针输出凸包上的点，每个点单独占一行。
每个CASE后空一行。

Sample Input

9
1 5
10 4
20 0
0 20
-1 16
-7 7
-1 3
-20 0
-18 1
0

Sample Output

-20 0
20 0
0 20

Author

John&GHOST

样例输入