当前位置：首页 > news >正文

UVa 596 The Incredible Hull

news 2026/6/25 17:25:35

题目描述

题目要求计算多个简单多边形的点集的凸包，并输出凸包的顶点。凸包顶点按逆时针顺序输出，起始点为xxx坐标最大的点（若相同取yyy最小的）。输出时保留所有共线的凸包顶点（即不删除共线点）。

输入格式

输入包含多行。每行以S、P或END开头。S开始一个新集合，后跟集合标识符。P定义一个多边形，后跟顶点数及坐标。END为最后一行。

输出格式

对于每个集合，输出一行标识符convex hull:，然后一行输出凸包顶点坐标，格式如(x,y)，顶点之间用空格分隔。

样例

输入

S Sample 1 P 5 8 0 8 8 0 8 5 6 2 3 P 3 6 13 2 18 2 13 P 4 15 6 15 14 10 14 10 6 S Sample 2 P 8 1 2 -3 5 1 8 -3 12 -7 8 -3 5 -7 2 -3 -2 S Sample 3 P 4 150 100 150 150 100 150 100 100 P 4 180 130 180 180 130 180 130 130 S Sample 4 P 4 20 5 10 10 0 5 10 0 P 4 20 20 10 25 0 20 10 15 P 4 20 35 10 40 0 35 10 30 END

输出

Sample 1 convex hull: (15,6) (15,14) (2,18) (0,8) (2,3) (8,0) Sample 2 convex hull: (1,2) (1,8) (-3,12) (-7,8) (-7,2) (-3,-2) Sample 3 convex hull: (180,130) (180,180) (130,180) (100,150) (100,100) (150,100) Sample 4 convex hull: (20,5) (20,20) (20,35) (10,40) (0,35) (0,20) (0,5) (10,0)

题目分析

本题的核心是计算点集的凸包，并保留共线点。可以使用Graham\texttt{Graham}Graham扫描法或Jarvis\texttt{Jarvis}Jarvis步进法。

算法

收集所有多边形的顶点，去重。
使用Jarvis\texttt{Jarvis}Jarvis步进法（礼品包装法）求凸包。在共线时，选择距离当前点最近的点，以保留所有共线顶点。
找到xxx最大（若相同则yyy最小）的点作为起始点，然后按逆时针顺序输出。

复杂度分析

顶点数≤20×20=400\le 20 \times 20 = 400≤20×20=400，Jarvis\texttt{Jarvis}JarvisO(nh)O(nh)O(nh)可接受。

代码实现

// The Incredible Hull// UVa ID: 596// Verdict: Accepted// Submission Date: 2016-08-13// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_VERTICES=500;structpoint{intx,y;booloperator<(constpoint&another)const{if(x!=another.x)returnx<another.x;elsereturny<another.y;}booloperator==(constpoint&another)const{returnx==another.x&&y==another.y;}};structpolygon{intvertexNumber;point vertex[MAX_VERTICES];};point vertex[MAX_VERTICES];intvertexPerObject,vertexOfTotal=0;// 叉积，判断点a，b，c组成的两条线段的转折方向。当叉积大于0，则形成一个右拐，否则共线（cp = 0）或左拐（cp < 0）intcp(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}// 从点a向点b望去，点c位于线段ab的右侧，返回trueboolcw(point a,point b,point c){returncp(a,b,c)<0;}// 从点a向点b望去，点c位于线段ab的左侧时，返回trueboolccw(point a,point b,point c){returncp(a,b,c)>0;}// 当三点共线时，返回trueboolcollinear(point a,point b,point c){returnabs(cp(a,b,c))==0;}intdistanceOfPoint(point a,point b){returnpow(a.x-b.x,2)+pow(a.y-b.y,2);}// Jarvis步进法求凸包voidjarvisConvexHull(){polygon pg;pg.vertexNumber=0;// 去掉重合点// 得到位置处于最左的点，当有共线情况存在时，取y坐标最小的，该顶点定为凸包上的顶点sort(vertex,vertex+vertexOfTotal);vertexOfTotal=unique(vertex,vertex+vertexOfTotal)-vertex;intcurrent=0,visited[MAX_VERTICES];memset(visited,0,sizeof(visited));do{// 寻找凸包的下一个候选顶点// 测试点current，next，i是否构成一个右转，或者共线// 当构成右转时，说明点i比next相对于current有更小的极角，应该将当前的待选凸包点更新为点i// 当共线时，因为题意要求输出共线的凸包顶点，故选择距离当前凸包点current更近的点intnext=0;for(inti=1;i<vertexOfTotal;i++){if(!visited[i]&&(cw(vertex[current],vertex[next],vertex[i])||distanceOfPoint(vertex[current],vertex[next])==0||(collinear(vertex[current],vertex[next],vertex[i])&&(distanceOfPoint(vertex[current],vertex[i])<distanceOfPoint(vertex[current],vertex[next])))))next=i;}// 将点next加入凸包pg.vertex[pg.vertexNumber++]=vertex[next];visited[next]=1;current=next;}while(current!=0);intselected=0;for(inti=0;i<pg.vertexNumber;i++)if(pg.vertex[i].x>pg.vertex[selected].x||(pg.vertex[i].x==pg.vertex[selected].x&&pg.vertex[i].y<pg.vertex[selected].y))selected=i;for(inti=selected;i<pg.vertexNumber+selected;i++)cout<<" ("<<pg.vertex[i%pg.vertexNumber].x<<','<<pg.vertex[i%pg.vertexNumber].y<<')';cout<<'\n';}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);charstart;while(cin>>start,start!='E'){string description;getline(cin,description);if(description.front()==' ')description.erase(description.begin());cout<<description<<" convex hull:\n";vertexOfTotal=0;while(cin>>start,start=='P'){cin>>vertexPerObject;for(inti=0;i<vertexPerObject;i++){cin>>vertex[vertexOfTotal].x>>vertex[vertexOfTotal].y;vertexOfTotal++;}}jarvisConvexHull();cin.putback(start);}return0;}