题目分析给定若干个点的坐标需要找到能够包围所有点的最小周长多边形即凸包并输出凸包上的所有点按顺时针方向首尾点相同以及凸包的周长。输入包含多组数据每组数据的第一行为点的数量nnn接下来nnn行每行两个实数表示坐标。当n0n 0n0时输入结束。输出格式要求每组数据输出三行以上第一行为Region #k:kkk从111开始。接下来一行或多行输出凸包上的所有点格式为(x,y)-连接首尾点相同点坐标四舍五入保留一位小数。最后一行输出周长格式为Perimeter length 保留两位小数的实数。两组数据之间用一个空行分隔。解题思路本题的核心是凸包Convex Hull\texttt{Convex Hull}Convex Hull算法。常用的凸包算法有Graham Scan\texttt{Graham Scan}Graham Scan格雷厄姆扫描法Andrew\texttt{Andrew}Andrew算法单调链法本题提供的代码使用了Graham\texttt{Graham}Graham扫描法的变体主要步骤如下排序首先按yyy坐标升序、xxx坐标升序排序找到最低最左的点作为参考点。极角排序以参考点为原点按极角从小到大排序若极角相同则按距离从小到大排序。构建凸包使用一个栈结构依次检查每个点如果新点使得最后两个点形成的向量呈顺时针方向即右转则弹出栈顶直到满足逆时针或共线条件然后将新点入栈。处理共线题目允许共线点以任意顺序输出因此算法中保留了共线点。输出方向题目要求顺时针输出代码在得到凸包后进行了reverse反转。周长计算依次累加相邻点的欧几里得距离。注意事项浮点数比较需要引入误差容忍值ϵ10−7\epsilon 10^{-7}ϵ10−7避免精度问题。当点数少于等于222时直接输出所有点此时凸包就是这些点本身。输出格式要求首尾点相同代码中在hull的最后已经包含了起始点。每组数据输出后需要加一个空行但最后一组数据后不能有多余空行代码通过if (cases)控制。代码实现// Moth Eradication// UVa ID: 218// Verdict: Accepted// Submission Date: 2016-04-30// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintEPSILON1E-7;// 浮点数比较误差阈值structpoint{doublex,y;// 点的坐标};point lowerLeftPoint;// 最低最左点作为极角排序的参考点// 叉积计算向量 AB 和 AC 的叉积doublecp(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}// 顺时针方向点 c 在线段 ab 的右侧boolcw(point a,point b,point c){returncp(a,b,c)-EPSILON;}// 逆时针方向点 c 在线段 ab 的左侧boolccw(point a,point b,point c){returncp(a,b,c)EPSILON;}// 三点共线boolcollinear(point a,point b,point c){returnfabs(cp(a,b,c))EPSILON;}// 判断是否逆时针或共线boolccwOrCollinear(point a,point b,point c){returnccw(a,b,c)||collinear(a,b,c);}// 排序函数先按 y 再按 x 升序用于找到最低最左点boollowerLeft(point a,point b){return(a.yb.y)?(a.xb.x):(a.yb.y);}// 判断两点坐标是否相同boolcmpPoint(point first,point second){returnfirst.xsecond.xfirst.ysecond.y;}// 计算点到参考点的距离平方避免开方用于极角相同时的比较doubledistanceToLowerLeftPoint(point p){returnpow(lowerLeftPoint.x-p.x,2)pow(lowerLeftPoint.y-p.y,2);}// 极角排序的比较函数boolsmallerAngle(point first,point second){// 如果三点共线距离近的排在前面if(collinear(lowerLeftPoint,first,second))returndistanceToLowerLeftPoint(first)distanceToLowerLeftPoint(second);// 否则按逆时针方向排序returnccw(lowerLeftPoint,first,second);}// Graham 凸包扫描算法voidgrahamConvexHull(vectorpointvertices,vectorpointhull){// 按 y 和 x 升序排序找到最低最左点sort(vertices.begin(),vertices.end(),lowerLeft);// 移除重复的点vertices.erase(unique(vertices.begin(),vertices.end(),cmpPoint),vertices.end());// 如果点数 2凸包就是所有点注意要闭合if(vertices.size()2){vertices.push_back(vertices[0]);// 添加首点形成闭合for(inti0;ivertices.size();i)hull.push_back(vertices[i]);return;}// 极角排序lowerLeftPointvertices[0];sort(vertices.begin()1,vertices.end(),smallerAngle);// 初始化栈放入前两个点inti2;hull.push_back(vertices[0]);hull.push_back(vertices[1]);// 添加哨兵最低最左点作为最后一个元素便于扫描结束时回到起点vertices.push_back(lowerLeftPoint);while(ivertices.size()-1){// 如果栈顶两点与新点形成顺时针方向右转则弹出栈顶if(cw(hull[hull.size()-2],hull.back(),vertices[i]))hull.erase(hull.end()-1);elsehull.push_back(vertices[i]);// 否则入栈}}// 计算两点之间的欧几里得距离doubledistances(point a,point b){returnsqrt(pow(a.x-b.x,2)pow(a.y-b.y,2));}intmain(){cin.tie(0);cin.sync_with_stdio(false);intn,cases0;while(cinn,n)// 读入 nn 0 时结束{vectorpointvertices;for(inti1;in;i){point a;cina.xa.y;vertices.push_back(a);}vectorpointhull;grahamConvexHull(vertices,hull);reverse(hull.begin(),hull.end());// 反转得到顺时针顺序if(cases)// 控制两组数据之间的空行coutendl;coutRegion #cases:endl;// 输出凸包上的点首尾点相同doublelength0.0;cout(fixedsetprecision(1)hull[0].x,fixedhull[0].y);for(inti1;ihull.size();i){cout-(fixedsetprecision(1)hull[i].x,fixedhull[i].y);lengthdistances(hull[i],hull[i-1]);}coutendl;coutPerimeter length fixedsetprecision(2)lengthendl;}return0;}