题目描述给定一个简单多边形可能为凸或凹的顶点序列按顺时针或逆时针顺序但输入要求按逆时针且最后一个点与第一个点重合要求计算其凸包最小凸多边形并输出凸包的顶点。若原多边形已是凸的则凸包为原多边形。输入包含多个数据集由-1分隔。输出需按指定格式先输出数据集个数再输出每个凸包的顶点数、顶点坐标最后以-1分隔不同数据集。输入格式第一行为一个正整数K KK表示数据集的个数。之后每个数据集的第一行为一个正整数N NN表示多边形顶点数。接下来N NN行每行两个整数表示顶点坐标。顶点按逆时针顺序给出最后一个顶点与第一个顶点重合即闭环。数据集之间用单独一行-1分隔。输出格式第一行输出K KK。然后对于每个数据集输出凸包的顶点数M 1 M 1M1注意输出格式要求M1即凸包顶点数加1 11因为要重复第一个点以闭合。然后输出M 1 M1M1行顶点坐标最后一行重复第一个点。数据集之间用-1分隔。样例输入3 15 30 30 50 60 60 20 70 45 86 39 112 60 200 113 250 50 300 200 130 240 76 150 47 76 36 40 33 35 30 30 -1 12 50 60 60 20 70 45 100 70 125 90 200 113 250 140 180 170 105 140 79 140 60 85 50 60 -1 6 60 20 250 140 180 170 79 140 50 60 60 20 -1 6 60 20 250 50 300 200 130 240 76 150 47 76 30 30 60 20 -1 6 60 20 250 140 180 170 79 140 50 60 60 20 6 60 20 250 140 180 170 79 140 5 60 60 20题目分析本题要求计算多边形的凸包。顶点数最多512 512512使用Andrew \texttt{Andrew}Andrew单调链算法O ( N log N ) O(N \log N)O(NlogN)即可。注意输入中顶点顺序为逆时针但算法不依赖顺序只需去重和排序。输出要求先输出数据集个数K KK。对每个凸包输出顶点数M MM实际为凸包顶点数 1 \ 11因为要闭合然后按逆时针顺序输出顶点坐标最后重复第一个点。数据集之间用-1分隔。解题思路读入K KK。对每个数据集读入N NN然后读入N NN个点。调用Andrew \texttt{Andrew}Andrew算法计算凸包得到凸包顶点列表不含重复起点。找到凸包中y yy坐标最小若相同则x xx最小的点作为输出起点确保输出顺序为逆时针。输出凸包顶点数 1 \ 11然后按逆时针顺序输出顶点最后重复起点。若不是最后一个数据集输出-1分隔。复杂度分析Andrew \texttt{Andrew}Andrew算法排序O ( N log N ) O(N \log N)O(NlogN)扫描O ( N ) O(N)O(N)N ≤ 512 N \le 512N≤512极快。代码实现// Convex Hull Finding// UVa ID: 681// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_VERTICES520;constintEPSILON0;structpoint{intx,y;booloperator(constpointanother)const{if(fabs(x-another.x)EPSILON)returnxanother.x;elsereturnyanother.y;}booloperator(constpointanother)const{returnfabs(x-another.x)EPSILONfabs(y-another.y)EPSILON;}};structpolygon{intnumberOfVertex;point vertex[MAX_VERTICES];};intcrossProduct(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}boolccw(point a,point b,point c){returncrossProduct(a,b,c)EPSILON;}boolcollinear(point a,point b,point c){returnfabs(crossProduct(a,b,c))EPSILON;}boolccwOrCollinear(point a,point b,point c){returnccw(a,b,c)||collinear(a,b,c);}polygonandrewConvexHull(point vertex[],intnumberOfVertex){polygon pg;if(numberOfVertex3){for(inti0;inumberOfVertex;i)pg.vertex[i]vertex[i];pg.numberOfVertexnumberOfVertex;returnpg;}sort(vertex,vertexnumberOfVertex);numberOfVertexunique(vertex,vertexnumberOfVertex)-vertex;point upper[MAX_VERTICES],lower[MAX_VERTICES];inttop;upper[0]vertex[0];upper[1]vertex[1];top2;for(inti2;inumberOfVertex;i){upper[top]vertex[i];while(top2ccwOrCollinear(upper[top-2],upper[top-1],upper[top])){upper[top-1]upper[top];top--;}top;}pg.numberOfVertex0;for(inti0;itop;i)pg.vertex[pg.numberOfVertex]upper[i];lower[0]vertex[numberOfVertex-1];lower[1]vertex[numberOfVertex-2];top2;for(intinumberOfVertex-3;i0;i--){lower[top]vertex[i];while(top2ccwOrCollinear(lower[top-2],lower[top-1],lower[top])){lower[top-1]lower[top];top--;}top;}for(inti1;itop-1;i)pg.vertex[pg.numberOfVertex]lower[i];returnpg;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);point tile[MAX_VERTICES];intnumberOfVertex;intk,delimiter;cink;coutk\n;for(inti1;ik;i){if(i1)cout-1\n;cinnumberOfVertex;for(intj0;jnumberOfVertex;j)cintile[j].xtile[j].y;cindelimiter;polygon containerandrewConvexHull(tile,numberOfVertex);intlowxcontainer.vertex[0].x,lowycontainer.vertex[0].y,lowi0;for(intj1;jcontainer.numberOfVertex;j)if(container.vertex[j].ylowy||(container.vertex[j].ylowycontainer.vertex[j].xlowx))lowxcontainer.vertex[j].x,lowycontainer.vertex[j].y,lowij;coutcontainer.numberOfVertex1\n;for(intjlowi;jlowi-container.numberOfVertex;j--){coutcontainer.vertex[(jcontainer.numberOfVertex)%container.numberOfVertex].x;cout container.vertex[(jcontainer.numberOfVertex)%container.numberOfVertex].y\n;}coutcontainer.vertex[lowi].x;cout container.vertex[lowi].y\n;}return0;}总结本题通过Andrew \texttt{Andrew}Andrew凸包算法计算多边形的凸包并按要求输出格式。关键点包括正确实现凸包算法并处理共线点。找到凸包上的最低点作为输出起点确保逆时针顺序。输出时重复起点以闭合多边形。数据集间用-1分隔。该解法是凸包计算的标准实现适用于顶点数较少的情况。
UVa 681 Convex Hull Finding
题目描述给定一个简单多边形可能为凸或凹的顶点序列按顺时针或逆时针顺序但输入要求按逆时针且最后一个点与第一个点重合要求计算其凸包最小凸多边形并输出凸包的顶点。若原多边形已是凸的则凸包为原多边形。输入包含多个数据集由-1分隔。输出需按指定格式先输出数据集个数再输出每个凸包的顶点数、顶点坐标最后以-1分隔不同数据集。输入格式第一行为一个正整数K KK表示数据集的个数。之后每个数据集的第一行为一个正整数N NN表示多边形顶点数。接下来N NN行每行两个整数表示顶点坐标。顶点按逆时针顺序给出最后一个顶点与第一个顶点重合即闭环。数据集之间用单独一行-1分隔。输出格式第一行输出K KK。然后对于每个数据集输出凸包的顶点数M 1 M 1M1注意输出格式要求M1即凸包顶点数加1 11因为要重复第一个点以闭合。然后输出M 1 M1M1行顶点坐标最后一行重复第一个点。数据集之间用-1分隔。样例输入3 15 30 30 50 60 60 20 70 45 86 39 112 60 200 113 250 50 300 200 130 240 76 150 47 76 36 40 33 35 30 30 -1 12 50 60 60 20 70 45 100 70 125 90 200 113 250 140 180 170 105 140 79 140 60 85 50 60 -1 6 60 20 250 140 180 170 79 140 50 60 60 20 -1 6 60 20 250 50 300 200 130 240 76 150 47 76 30 30 60 20 -1 6 60 20 250 140 180 170 79 140 50 60 60 20 6 60 20 250 140 180 170 79 140 5 60 60 20题目分析本题要求计算多边形的凸包。顶点数最多512 512512使用Andrew \texttt{Andrew}Andrew单调链算法O ( N log N ) O(N \log N)O(NlogN)即可。注意输入中顶点顺序为逆时针但算法不依赖顺序只需去重和排序。输出要求先输出数据集个数K KK。对每个凸包输出顶点数M MM实际为凸包顶点数 1 \ 11因为要闭合然后按逆时针顺序输出顶点坐标最后重复第一个点。数据集之间用-1分隔。解题思路读入K KK。对每个数据集读入N NN然后读入N NN个点。调用Andrew \texttt{Andrew}Andrew算法计算凸包得到凸包顶点列表不含重复起点。找到凸包中y yy坐标最小若相同则x xx最小的点作为输出起点确保输出顺序为逆时针。输出凸包顶点数 1 \ 11然后按逆时针顺序输出顶点最后重复起点。若不是最后一个数据集输出-1分隔。复杂度分析Andrew \texttt{Andrew}Andrew算法排序O ( N log N ) O(N \log N)O(NlogN)扫描O ( N ) O(N)O(N)N ≤ 512 N \le 512N≤512极快。代码实现// Convex Hull Finding// UVa ID: 681// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_VERTICES520;constintEPSILON0;structpoint{intx,y;booloperator(constpointanother)const{if(fabs(x-another.x)EPSILON)returnxanother.x;elsereturnyanother.y;}booloperator(constpointanother)const{returnfabs(x-another.x)EPSILONfabs(y-another.y)EPSILON;}};structpolygon{intnumberOfVertex;point vertex[MAX_VERTICES];};intcrossProduct(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}boolccw(point a,point b,point c){returncrossProduct(a,b,c)EPSILON;}boolcollinear(point a,point b,point c){returnfabs(crossProduct(a,b,c))EPSILON;}boolccwOrCollinear(point a,point b,point c){returnccw(a,b,c)||collinear(a,b,c);}polygonandrewConvexHull(point vertex[],intnumberOfVertex){polygon pg;if(numberOfVertex3){for(inti0;inumberOfVertex;i)pg.vertex[i]vertex[i];pg.numberOfVertexnumberOfVertex;returnpg;}sort(vertex,vertexnumberOfVertex);numberOfVertexunique(vertex,vertexnumberOfVertex)-vertex;point upper[MAX_VERTICES],lower[MAX_VERTICES];inttop;upper[0]vertex[0];upper[1]vertex[1];top2;for(inti2;inumberOfVertex;i){upper[top]vertex[i];while(top2ccwOrCollinear(upper[top-2],upper[top-1],upper[top])){upper[top-1]upper[top];top--;}top;}pg.numberOfVertex0;for(inti0;itop;i)pg.vertex[pg.numberOfVertex]upper[i];lower[0]vertex[numberOfVertex-1];lower[1]vertex[numberOfVertex-2];top2;for(intinumberOfVertex-3;i0;i--){lower[top]vertex[i];while(top2ccwOrCollinear(lower[top-2],lower[top-1],lower[top])){lower[top-1]lower[top];top--;}top;}for(inti1;itop-1;i)pg.vertex[pg.numberOfVertex]lower[i];returnpg;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);point tile[MAX_VERTICES];intnumberOfVertex;intk,delimiter;cink;coutk\n;for(inti1;ik;i){if(i1)cout-1\n;cinnumberOfVertex;for(intj0;jnumberOfVertex;j)cintile[j].xtile[j].y;cindelimiter;polygon containerandrewConvexHull(tile,numberOfVertex);intlowxcontainer.vertex[0].x,lowycontainer.vertex[0].y,lowi0;for(intj1;jcontainer.numberOfVertex;j)if(container.vertex[j].ylowy||(container.vertex[j].ylowycontainer.vertex[j].xlowx))lowxcontainer.vertex[j].x,lowycontainer.vertex[j].y,lowij;coutcontainer.numberOfVertex1\n;for(intjlowi;jlowi-container.numberOfVertex;j--){coutcontainer.vertex[(jcontainer.numberOfVertex)%container.numberOfVertex].x;cout container.vertex[(jcontainer.numberOfVertex)%container.numberOfVertex].y\n;}coutcontainer.vertex[lowi].x;cout container.vertex[lowi].y\n;}return0;}总结本题通过Andrew \texttt{Andrew}Andrew凸包算法计算多边形的凸包并按要求输出格式。关键点包括正确实现凸包算法并处理共线点。找到凸包上的最低点作为输出起点确保逆时针顺序。输出时重复起点以闭合多边形。数据集间用-1分隔。该解法是凸包计算的标准实现适用于顶点数较少的情况。
