题目描述给定一个多边形的顶点坐标序列可能包含重复点求该多边形的最小凸包凸包即包含所有点的最小凸多边形且凸包边的转角小于180∘180^\circ180∘。输出凸包的顶点坐标要求以输入序列中第一个属于凸包的点作为起点按逆时针顺序输出。每组数据之间用空行分隔。输入格式多组数据每组数据包含若干行每行两个整数用逗号和空格分隔表示一个点坐标。每个数据集中至少包含333个不同的点。数据集之间由一个空行分隔。输出格式对于每组数据输出凸包的顶点坐标每行一个点格式为x, y按逆时针顺序起点为输入序列中第一个属于凸包的点。每组输出之间用空行分隔。样例输入0, 0 2, 0 1, 1 2, 2 0, 2 0, 0输出0, 0 2, 0 2, 2 0, 2 0, 0题目分析本题要求计算给定点集的凸包。由于数据量未知但可使用经典的Andrew\texttt{Andrew}Andrew单调链算法O(nlog⁡n)O(n \log n)O(nlogn)或Jarvis\texttt{Jarvis}Jarvis步进法O(nh)O(nh)O(nh)hhh为凸包点数。输出要求按逆时针顺序且起点为输入序列中第一个在凸包上的点。注意可能有多点共线需要剔除共线中间点只保留凸包端点。解题思路去重输入可能包含重复点先排序去重。Andrew\texttt{Andrew}Andrew算法按(x, y)排序。构建下凸包从左到右维护栈保证新点使栈顶两点的叉积≥0\ge 0≥0左转或共线删除共线中间点。构建上凸包从右到左类似。合并上下凸包得到完整凸包按逆时针顺序但Andrew\texttt{Andrew}Andrew算法默认输出顺序为顺时针但起始点不一定满足要求需调整。确定起点在输入序列中查找第一个属于凸包的点记录其在凸包中的索引。调整顺序Andrew\texttt{Andrew}Andrew算法输出为顺时针顺序需反转方向。复杂度分析Andrew\texttt{Andrew}Andrew算法排序O(nlog⁡n)O(n \log n)O(nlogn)扫描O(n)O(n)O(n)。总时间O(nlog⁡n)O(n \log n)O(nlogn)。代码实现// Convex Hull of the Polygon// UVa ID: 675// Verdict: Accepted// Submission Date: 2017-06-07// UVa Run Time: 0.110s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{intx,y;booloperator(constpointp)const{if(y!p.y)returnyp.y;returnxp.x;}booloperator(constpointp)const{returnxp.xyp.y;}};constintMAX_VERTICES100005;typedefvectorpointpolygon;intcp(pointa,pointb,pointc){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}boolccwOrCollinear(pointa,pointb,pointc){returncp(a,b,c)0;}polygonandrewConvexHull(polygonvertices){sort(vertices.begin(),vertices.end());point ch[MAX_VERTICES];inttop0;for(inti0;ivertices.size();i){while(top2ccwOrCollinear(ch[top-2],ch[top-1],vertices[i]))top--;ch[top]vertices[i];}for(intivertices.size()-1,uppertop1;i0;i--){while(topupperccwOrCollinear(ch[top-2],ch[top-1],vertices[i]))top--;ch[top]vertices[i];}polygon pg;for(inti0;itop-1;i)pg.push_back(ch[i]);returnpg;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;string separator;istringstream iss;intcases0;while(getline(cin,line),line.length()0){polygon source,vertices;do{intx10,y10;iss.clear();iss.str(line);issx1separatory1;vertices.push_back(point{x1,y1});source.push_back(point{x1,y1});}while(getline(cin,line),line.length()0);polygon convexHullandrewConvexHull(vertices);intstart-1;for(inti0;isource.size()start-1;i)for(intj0;jconvexHull.size();j)if(source[i]convexHull[j]){startj;break;}if(cases0)cout\n;inttotalconvexHull.size();for(inti0;itotal;i){intj(totalstart-i)%total;coutconvexHull[j].x, convexHull[j].y\n;}coutconvexHull[start].x, convexHull[start].y\n;}return0;}总结本题通过Andrew\texttt{Andrew}Andrew单调链算法计算凸包并按要求调整输出顺序和起点。关键点包括正确去除共线中间点。找到输入序列中第一个在凸包上的点。按逆时针顺序输出起点重复一次以闭合多边形。该解法是凸包计算的经典实现适用于点集规模较大的情况。