肥城市网站建设工作啦

肥城市网站建设,工作啦,装修互联网营销公司,网站搭建报价题目描述 给定 NNN (0N≤20000 N \le 20000N≤2000) 个位于同一圆周上的点#xff0c;这些点所在圆的圆心是原点。你的任务是找出这些点能够构成多少个不同边数的正多边形。例如#xff0c;如果有 666 个点恰好是一个正六边形的顶点#xff0c;那么就说这些点构…题目描述给定NNN(0N≤20000 N \le 20000N≤2000) 个位于同一圆周上的点这些点所在圆的圆心是原点。你的任务是找出这些点能够构成多少个不同边数的正多边形。例如如果有666个点恰好是一个正六边形的顶点那么就说这些点构成了一个正六边形。输入格式输入最多包含101010组数据。每组数据以一个整数NNN开始表示点的数量。接下来NNN行每行给出一个点的笛卡尔坐标(x,y)(x, y)(x,y)浮点数至少精确到九位小数。所有点都在同一个以原点为圆心的圆上任意两点坐标不同。如果两个点相对于圆心的角距离小于10−810^{-8}10−8弧度则认为它们是同一个点。输入以N0N 0N0结束。输出格式对于每组数据首先输出Case X:XXX为序号。接下来若干行每行输出两个整数SSS和FFF其中SSS是正多边形的边数FFF是该正多边形被构成的次数。输出按SSS升序排列只输出实际出现的边数。题目分析1. 问题转化所有点都在以原点为圆心的同一个圆上因此每个点可以由其极角唯一确定模2π2\pi2π。设点PiP_iPi​的极角为θi\theta_iθi​满足0≤θi2π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个不同的角度。对于每个可能的边数kkkkkk至少为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计算目标角度θij⋅Δ\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。枚举边数kkkO(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)在N2000N2000N2000时可能达到约101010^{10}1010量级显然不可接受。优化思路实际上由于kkk必须整除mmm才有可能构成正多边形因为需要kkk个点我们可以只检查mmm的因子kkkk≥3k \ge 3k≥3。但即使如此最坏情况m2000m2000m2000时因子个数不多约404040个但枚举起点和检查的复杂度仍较高。然而本题实际测试数据较弱上述直接枚举法可以通过。在更严格的情况下我们可能需要利用哈希表来快速判断某个角度是否存在将检查等差数列的复杂度降为O(k)O(k)O(k)从而总复杂度降为O(m2log⁡m)O(m^2 \log m)O(m2logm)或更低。解题思路总结读入与预处理计算每个点的极角归一化到[0,2π)[0, 2\pi)[0,2π)排序并去重容差ϵ10−8\epsilon 10^{-8}ϵ10−8。扩展数组为了处理圆周循环将去重后的角度数组复制一份每个角度加2π2\pi2π得到扩展数组。枚举检查对于每个边数kkk3≤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避免重复计数。输出结果按SSS升序输出所有F0F0F0的结果。注意事项浮点数比较必须使用容差不能直接使用。正多边形的顶点必须全部来自输入点且必须恰好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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoublePIacos(-1.0);constdoubleEPS1e-8;constdoubleTWO_PI2.0*PI;intmain(){intcaseNo1;intn;while(scanf(%d,n)1n!0){vectordoubleangles;for(inti0;in;i){doublex,y;scanf(%lf %lf,x,y);doubleangatan2(y,x);if(ang0)angTWO_PI;// 转换到 [0, 2π)angles.push_back(ang);}sort(angles.begin(),angles.end());// 去重基于容差vectordoubleuniqueAngles;for(doubleang:angles){if(uniqueAngles.empty()||fabs(ang-uniqueAngles.back())EPS)uniqueAngles.push_back(ang);}intmuniqueAngles.size();// 将角度复制一份加上 2π便于处理循环vectordoubleextendeduniqueAngles;for(doubleang:uniqueAngles)extended.push_back(angTWO_PI);vectorpairint,intresults;// 检查每个可能的边数 k至少 3 条边for(intk3;km;k){doublestepTWO_PI/k;intcount0;// 枚举起始点for(intstart0;startm;start){doublecurrentextended[start];booloktrue;for(intj1;jk;j){currentstep;// 在 extended 中查找是否存在接近 current 的角度autoitlower_bound(extended.begin(),extended.end(),current-EPS);if(itextended.end()||fabs(*it-current)EPS){okfalse;break;}}if(ok)count;}if(count0)results.push_back({k,count/k});// 注意由于正多边形每个顶点作为起点都会被计数一次所以总数要除以 k}printf(Case %d:\n,caseNo);for(autop:results)printf(%d %d\n,p.first,p.second);}return0;}代码解读PI、EPS、TWO_PI为常量便于使用。主循环读入每组数据直到N0N0N0。计算极角并使用atan2将负角加上2π2\pi2π归一化。排序后去重得到真正不同的角度列表uniqueAngles。创建扩展数组extended包含原角度和每个角度加2π2\pi2π便于二分查找时处理循环。对于每个kkk计算步长step枚举起点检查是否存在公差为step的等差数列。使用lower_bound进行二分查找判断目标角度是否存在容差比较。统计结果时注意除以kkk以避免因不同起点而重复计数。最后按格式输出。总结本题的关键在于将几何问题转化为在极角序列中寻找等差数列的问题。通过极角归一化、排序去重、扩展数组处理循环以及二分查找我们可以高效地判断是否存在正多边形。虽然直接枚举法的理论复杂度较高但由于数据限制和实际测试数据较弱该代码可以通过。在更严格的情况下可以考虑只枚举mmm的因子kkk并使用哈希表进一步优化查找过程。