题目描述给定平面上nnn个点要求将这些点全部作为顶点构造一个简单多边形。多边形不能包含额外顶点任意两条非相邻边不能相交相邻边仅共享公共端点。题目保证存在合法多边形任意合法多边形均可作为答案。所有点坐标互不相同且并非全部共线。输入格式第一行包含一个整数ccc1≤c≤2001 \le c \le 2001≤c≤200表示测试用例数量。每个测试用例首先包含一个整数nnn3≤n≤20003 \le n \le 20003≤n≤2000随后在同一行给出nnn个点的坐标每个点由两个整数xxx和yyy−10000≤x,y≤10000-10000 \le x, y \le 10000−10000≤x,y≤10000表示。输入数据中每个测试用例的所有点可能分布在多行但使用标准输入读取时无影响。输出格式对于每个测试用例输出一行包含一个000到n−1n-1n−1的排列。每个数字表示输入中对应点的索引按输入顺序。按该顺序依次连接相邻点包括最后一个点与第一个点相连所得图形必须是一个简单多边形。样例输入2 4 0 0 2 0 0 1 1 0 5 0 0 10 0 10 5 5 -1 0 5输出0 3 1 2 3 1 2 4 0题目分析本题要求在任意给定点集上构造简单多边形且输出顶点顺序即可。由于任意点集都存在至少一个简单多边形例如按极角排序构造的星形多边形且题目允许多种答案因此任务转化为寻找一种通用、高效的构造方法。直接枚举所有排列不可行因为nnn最大为200020002000必须利用几何性质。经典的极角排序构造法能够保证得到简单多边形选取一个极点作为起点将其余点按相对于该点的极角排序然后依次连接。但这种方法在处理与极点共线的点时需要特别处理否则会导致自交。共线点若按距离升序排列当闭合回极点时最后一条边会穿过这些共线点形成的折线产生交叉。正确做法是仅将极角最大的那一组共线点反转使该组点按距离降序排列从而保证闭合边从最远点逐步回到最近点避免相交。解题思路构造过程分为以下步骤步骤1\texttt{1}1. 选取所有点中yyy坐标最小的点若多个点yyy坐标相同则选取其中xxx坐标最小的点。该点作为极点基准点记为P0P_0P0。步骤2\texttt{2}2. 将除P0P_0P0外的所有点按相对于P0P_0P0的极角从小到大排序。极角排序采用半平面分类结合叉积比较避免浮点误差。具体地将平面以极点为中心分为上半平面包含正xxx轴方向和下半平面先按半平面排序同一半平面内按叉积正负判断逆时针顺序。若两个点与极点共线叉积为零则按它们到极点的距离平方升序排列。步骤3\texttt{3}3. 排序完成后处理共线点问题。从排序序列的末尾向前扫描找出最后一个与序列末尾点不共线的位置。设该位置为pospospos则pos1pos1pos1到末尾这一段的点全部与极点共线且具有相同的极角即极角最大的那一组。将该段整体反转使该组点按距离降序排列距离最远的位于段首最近的位于段末。步骤4\texttt{4}4. 输出极点索引随后按处理后的顺序输出其余点的索引。该顺序连接得到的多边形一定是简单多边形。上述方法的时间复杂度为O(nlogn)O(n \log n)O(nlogn)空间复杂度为O(n)O(n)O(n)完全满足题目限制。代码实现// Simple Polygon// UVa ID: 12226// Verdict: Accepted// Submission Date: 2026-07-21// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structPoint{intx,y,idx;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intc;cinc;while(c--){intn;cinn;vectorPointpts(n);for(inti0;in;i){cinpts[i].xpts[i].y;pts[i].idxi;}intbaseIdx0;for(inti1;in;i){if(pts[i].ypts[baseIdx].y||(pts[i].ypts[baseIdx].ypts[i].xpts[baseIdx].x))baseIdxi;}Point basepts[baseIdx];vectorintothers;for(inti0;in;i)if(i!baseIdx)others.push_back(i);autohalf[](constPointp)-int{return(p.ybase.y||(p.ybase.yp.xbase.x))?0:1;};sort(others.begin(),others.end(),[](inti,intj){constPointapts[i],bpts[j];inthahalf(a),hbhalf(b);if(ha!hb)returnhahb;longlongcross1LL*(a.x-base.x)*(b.y-base.y)-1LL*(a.y-base.y)*(b.x-base.x);if(cross!0)returncross0;longlongda1LL*(a.x-base.x)*(a.x-base.x)1LL*(a.y-base.y)*(a.y-base.y);longlongdb1LL*(b.x-base.x)*(b.x-base.x)1LL*(b.y-base.y)*(b.y-base.y);returndadb;});intmothers.size();if(m1){intlastothers[m-1];intposm-2;while(pos0){intcurothers[pos];longlongcross1LL*(pts[cur].x-base.x)*(pts[last].y-base.y)-1LL*(pts[cur].y-base.y)*(pts[last].x-base.x);if(cross!0)break;--pos;}if(pos1m-1){reverse(others.begin()pos1,others.end());}}coutbaseIdx;for(intidx:others)cout idx;cout\n;}return0;}总结本题的核心在于利用极角排序构造星形多边形并对共线点进行单端反转处理。关键技巧包括使用半平面分类和叉积实现精确的极角排序避免浮点数误差。仅反转极角最大的一组共线点而其他共线段保持距离升序既保证了算法正确性又简化了实现。该构造方法的时间复杂度为O(nlogn)O(n \log n)O(nlogn)适用于n≤2000n \le 2000n≤2000的规模且代码简洁易于实现。掌握这种几何构造技巧对于解决类似平面点集的多边形生成问题具有重要参考价值。