UVa 596 The Incredible Hull

题目描述题目要求计算多个简单多边形的点集的凸包并输出凸包的顶点。凸包顶点按逆时针顺序输出起始点为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×20400\le 20 \times 20 400≤20×20400Jarvis\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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_VERTICES500;structpoint{intx,y;booloperator(constpointanother)const{if(x!another.x)returnxanother.x;elsereturnyanother.y;}booloperator(constpointanother)const{returnxanother.xyanother.y;}};structpolygon{intvertexNumber;point vertex[MAX_VERTICES];};point vertex[MAX_VERTICES];intvertexPerObject,vertexOfTotal0;// 叉积判断点abc组成的两条线段的转折方向。当叉积大于0则形成一个右拐否则共线cp 0或左拐cp 0intcp(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.vertexNumber0;// 去掉重合点// 得到位置处于最左的点当有共线情况存在时取y坐标最小的该顶点定为凸包上的顶点sort(vertex,vertexvertexOfTotal);vertexOfTotalunique(vertex,vertexvertexOfTotal)-vertex;intcurrent0,visited[MAX_VERTICES];memset(visited,0,sizeof(visited));do{// 寻找凸包的下一个候选顶点// 测试点currentnexti是否构成一个右转或者共线// 当构成右转时说明点i比next相对于current有更小的极角应该将当前的待选凸包点更新为点i// 当共线时因为题意要求输出共线的凸包顶点故选择距离当前凸包点current更近的点intnext0;for(inti1;ivertexOfTotal;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])))))nexti;}// 将点next加入凸包pg.vertex[pg.vertexNumber]vertex[next];visited[next]1;currentnext;}while(current!0);intselected0;for(inti0;ipg.vertexNumber;i)if(pg.vertex[i].xpg.vertex[selected].x||(pg.vertex[i].xpg.vertex[selected].xpg.vertex[i].ypg.vertex[selected].y))selectedi;for(intiselected;ipg.vertexNumberselected;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(cinstart,start!E){string description;getline(cin,description);if(description.front() )description.erase(description.begin());coutdescription convex hull:\n;vertexOfTotal0;while(cinstart,startP){cinvertexPerObject;for(inti0;ivertexPerObject;i){cinvertex[vertexOfTotal].xvertex[vertexOfTotal].y;vertexOfTotal;}}jarvisConvexHull();cin.putback(start);}return0;}