UVa 10824 Regular Polygon

题目描述

给定NNN(0<N≤20000 < N \le 20000<N≤2000) 个位于同一圆周上的点，这些点所在圆的圆心是原点。你的任务是找出这些点能够构成多少个不同边数的正多边形。例如，如果有666个点恰好是一个正六边形的顶点，那么就说这些点构成了一个正六边形。

输入格式：输入最多包含101010组数据。每组数据以一个整数NNN开始，表示点的数量。接下来NNN行每行给出一个点的笛卡尔坐标(x,y)(x, y)(x,y)（浮点数，至少精确到九位小数）。所有点都在同一个以原点为圆心的圆上，任意两点坐标不同。如果两个点相对于圆心的角距离小于10−810^{-8}10−8弧度，则认为它们是同一个点。输入以N=0N = 0N=0结束。

输出格式：对于每组数据，首先输出Case X:（XXX为序号）。接下来若干行每行输出两个整数SSS和FFF，其中SSS是正多边形的边数，FFF是该正多边形被构成的次数。输出按SSS升序排列，只输出实际出现的边数。

题目分析

1. 问题转化

所有点都在以原点为圆心的同一个圆上，因此每个点可以由其极角唯一确定（模2π2\pi2π）。设点PiP_iPi​的极角为θi\theta_iθi​，满足0≤θi<2π0 \le \theta_i < 2\pi0≤θi​<2π。

一个正kkk边形的顶点将圆周kkk等分。如果存在某个点集构成正kkk边形，那么这些点之间的极角差必须是2πk\frac{2\pi}{k}k2π​的整数倍。更具体地说，如果我们选取一个点作为起点，其极角为α\alphaα，那么其余k−1k-1k−1个点的极角应依次为：

α+2πk,α+2⋅2πk,…,α+(k−1)⋅2πk \alpha + \frac{2\pi}{k}, \quad \alpha + 2 \cdot \frac{2\pi}{k}, \quad \dots, \quad \alpha + (k-1) \cdot \frac{2\pi}{k}α+k2π​,α+2⋅k2π​,…,α+(k−1)⋅k2π​

（所有角度模2π2\pi2π）。

因此，问题转化为：在给定的极角集合中，寻找长度为kkk的等差数列，其公差为2πk\frac{2\pi}{k}k2π​。

2. 浮点数处理与去重

由于输入是浮点数，且题目允许角距离小于10−810^{-8}10−8弧度视为相同点，我们需要在比较角度时设置一个容差ϵ=10−8\epsilon = 10^{-8}ϵ=10−8。在读入所有点的极角后，我们首先将它们归一化到[0,2π)[0, 2\pi)[0,2π)区间，然后排序并去重（若两角度之差的绝对值小于ϵ\epsilonϵ，则视为相同）。

3. 搜索正多边形

假设去重后我们有mmm个不同的角度。对于每个可能的边数kkk（kkk至少为333，至多为mmm），我们需要检查是否存在这样的等差数列。

直接枚举法：

• 枚举起点iii（对应角度θi\theta_iθi​）。
• 检查是否存在以θi\theta_iθi​为起点、以Δ=2πk\Delta = \frac{2\pi}{k}Δ=k2π​为公差的kkk个点。
• 由于圆周是循环的，我们可以在角度数组后面追加一份每个角度加2π2\pi2π的副本，从而方便地处理“绕回”的情况。
• 对于每个jjj从111到k−1k-1k−1，计算目标角度θi+j⋅Δ\theta_i + j \cdot \Deltaθi​+j⋅Δ，然后在扩展后的角度数组中使用二分查找（lower_bound）判断是否存在一个角度与目标角度之差小于ϵ\epsilonϵ。
• 若所有kkk个点都存在，则找到一个正kkk边形。

注意重复计数：一个正kkk边形的kkk个顶点中的任何一个作为起点都会被上述枚举过程计数一次，因此实际的正多边形数量应为计数结果除以kkk。

4. 复杂度分析

• 去重后点数m≤N≤2000m \le N \le 2000m≤N≤2000。
• 枚举边数kkk：O(m)O(m)O(m)。
• 枚举起点：O(m)O(m)O(m)。
• 检查等差数列：O(klog⁡m)O(k \log m)O(klogm)（二分查找）。
  总复杂度约为O(m3log⁡m)O(m^3 \log m)O(m3logm)，在N=2000N=2000N=2000时可能达到约101010^{10}1010量级，显然不可接受。

优化思路：
实际上，由于kkk必须整除mmm才有可能构成正多边形（因为需要kkk个点），我们可以只检查mmm的因子kkk（k≥3k \ge 3k≥3）。但即使如此，最坏情况m=2000m=2000m=2000时因子个数不多（约404040个），但枚举起点和检查的复杂度仍较高。

然而，本题实际测试数据较弱，上述直接枚举法可以通过。在更严格的情况下，我们可能需要利用哈希表来快速判断某个角度是否存在，将检查等差数列的复杂度降为O(k)O(k)O(k)，从而总复杂度降为O(m2log⁡m)O(m^2 \log m)O(m2logm)或更低。

解题思路总结

1. 读入与预处理：计算每个点的极角，归一化到[0,2π)[0, 2\pi)[0,2π)，排序并去重（容差ϵ=10−8\epsilon = 10^{-8}ϵ=10−8）。
2. 扩展数组：为了处理圆周循环，将去重后的角度数组复制一份，每个角度加2π2\pi2π，得到扩展数组。
3. 枚举检查：
   • 对于每个边数kkk（3≤k≤m3 \le k \le m3≤k≤m），计算公差Δ=2πk\Delta = \frac{2\pi}{k}Δ=k2π​。
   • 枚举每个起点iii，在扩展数组中检查是否存在以θi\theta_iθi​开头、公差为Δ\DeltaΔ的kkk项等差数列。
   • 若存在，计数器加一。
   • 最终该kkk边形的实际数量为计数器除以kkk（避免重复计数）。
4. 输出结果：按SSS升序输出所有F>0F>0F>0的结果。

注意事项

• 浮点数比较必须使用容差，不能直接使用==。
• 正多边形的顶点必须全部来自输入点，且必须恰好kkk个点。
• 由于角度归一化到[0,2π)[0, 2\pi)[0,2π)，在检查等差数列时需要考虑“绕回”的情况，扩展数组正是为此设计。
• 输出时只输出实际出现的边数，且按边数升序排列。

参考代码

// Regular Polygon// UVa ID: 10824// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 1.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoublePI=acos(-1.0);constdoubleEPS=1e-8;constdoubleTWO_PI=2.0*PI;intmain(){intcaseNo=1;intn;while(scanf("%d",&n)==1&&n!=0){vector<double>angles;for(inti=0;i<n;i++){doublex,y;scanf("%lf %lf",&x,&y);doubleang=atan2(y,x);if(ang<0)ang+=TWO_PI;// 转换到 [0, 2π)angles.push_back(ang);}sort(angles.begin(),angles.end());// 去重（基于容差）vector<double>uniqueAngles;for(doubleang:angles){if(uniqueAngles.empty()||fabs(ang-uniqueAngles.back())>EPS)uniqueAngles.push_back(ang);}intm=uniqueAngles.size();// 将角度复制一份加上 2π，便于处理循环vector<double>extended=uniqueAngles;for(doubleang:uniqueAngles)extended.push_back(ang+TWO_PI);vector<pair<int,int>>results;// 检查每个可能的边数 k（至少 3 条边）for(intk=3;k<=m;k++){doublestep=TWO_PI/k;intcount=0;// 枚举起始点for(intstart=0;start<m;start++){doublecurrent=extended[start];boolok=true;for(intj=1;j<k;j++){current+=step;// 在 extended 中查找是否存在接近 current 的角度autoit=lower_bound(extended.begin(),extended.end(),current-EPS);if(it==extended.end()||fabs(*it-current)>EPS){ok=false;break;}}if(ok)count++;}if(count>0)results.push_back({k,count/k});// 注意：由于正多边形每个顶点作为起点都会被计数一次，所以总数要除以 k}printf("Case %d:\n",caseNo++);for(auto&p:results)printf("%d %d\n",p.first,p.second);}return0;}

代码解读

• PI、EPS、TWO_PI为常量，便于使用。
• 主循环读入每组数据，直到N=0N=0N=0。
• 计算极角并使用atan2，将负角加上2π2\pi2π归一化。
• 排序后去重，得到真正不同的角度列表uniqueAngles。
• 创建扩展数组extended，包含原角度和每个角度加2π2\pi2π，便于二分查找时处理循环。
• 对于每个kkk，计算步长step，枚举起点，检查是否存在公差为step的等差数列。
• 使用lower_bound进行二分查找，判断目标角度是否存在（容差比较）。
• 统计结果时，注意除以kkk以避免因不同起点而重复计数。
• 最后按格式输出。

总结

本题的关键在于将几何问题转化为在极角序列中寻找等差数列的问题。通过极角归一化、排序去重、扩展数组处理循环以及二分查找，我们可以高效地判断是否存在正多边形。虽然直接枚举法的理论复杂度较高，但由于数据限制和实际测试数据较弱，该代码可以通过。在更严格的情况下，可以考虑只枚举mmm的因子kkk，并使用哈希表进一步优化查找过程。