企业官网建设流程全解析

题目描述

在圆边界上随机取三个点，它们构成锐角三角形的概率为0.250.250.25。教授Neal Wu\texttt{Neal Wu}Neal Wu希望通过实验验证该结果。传统方法需重复实验极多次（如101810^{18}1018次），耗时过长。他发现可以一次性生成nnn个点，利用所有三点组合（共N=n(n−1)(n−2)6N = \frac{n(n-1)(n-2)}{6}N=6n(n−1)(n−2)​个三角形）统计锐角三角形个数MMM，则概率即为M/NM/NM/N。给定圆上的nnn个点（以角度给出），请计算锐角三角形数量。

输入格式

输入包含约404040个测试用例。每个用例以两个正整数nnn（0<n≤200000 < n \le 200000<n≤20000）和rrr（0<r≤5000 < r \le 5000<r≤500）开头，圆心在原点(0,0)(0,0)(0,0)。接下来nnn行，每行一个浮点数θ\thetaθ（0.000≤θ<360.0000.000 \le \theta < 360.0000.000≤θ<360.000），表示该点与xxx轴正方向所成的角度（度），其坐标即为(rcos⁡θ,rsin⁡θ)(r\cos\theta, r\sin\theta)(rcosθ,rsinθ)。θ\thetaθ精确到三位小数，且无重复点。输入以一行0 0结束。

输出格式

对每个测试用例，输出一行Case X: Y，其中XXX为序号（从111开始），YYY为锐角三角形数量。

样例

输入

4 71 234.600 33.576 20.375 84.908 7 7 11.586 114.435 248.411 108.640 287.629 150.224 340.481 0 0

输出

Case 1: 2 Case 2: 12

题目分析

圆上任意三点确定一个三角形。设三点将圆周分成三段弧，对应的圆心角分别为α,β,γ\alpha, \beta, \gammaα,β,γ，满足α+β+γ=360∘\alpha+\beta+\gamma=360^\circα+β+γ=360∘。

• 若α,β,γ\alpha, \beta, \gammaα,β,γ均小于180∘180^\circ180∘，则三角形为锐角三角形。
• 若恰好有一段等于180∘180^\circ180∘，则三角形为直角三角形（此时该弧所对的边为直径，由泰勒斯定理可知）。
• 若某一段大于180∘180^\circ180∘，则三角形为钝角三角形。

直接枚举所有三点组合O(n3)O(n^3)O(n3)不可行（n≤20000n\le 20000n≤20000）。需要利用补集思想：
锐角数 = 总三角形数 − 钝角三角形数 − 直角三角形数。

钝角三角形的计数

钝角三角形有且仅有一个钝角顶点。以该顶点为起点，逆时针方向看，另外两个点必须都落在小于180∘180^\circ180∘的范围内。因此，对于每个点iii，设其逆时针方向严格小于180∘180^\circ180∘内的点数为cic_ici​，则从这cic_ici​个点中任选两个与iii组成的三角形均为钝角三角形，且每个钝角三角形被其钝角顶点唯一计数。所以钝角三角形总数O=∑i(ci2)O = \sum_i \binom{c_i}{2}O=∑i​(2ci​​)。

直角三角形的计数

直角三角形由一条直径（即一对对径点）和圆周上任意第三个点构成。设对径点对数为DDD，则直角三角形数R=D×(n−2)R = D \times (n-2)R=D×(n−2)。
对径点：两角度之差恰好为180∘180^\circ180∘（对应整数表示下差值为180000180000180000）。

因此，锐角数A=T−O−RA = T - O - RA=T−O−R，其中T=n(n−1)(n−2)6T = \frac{n(n-1)(n-2)}6T=6n(n−1)(n−2)​。

解题思路

角度处理

输入角度为三位小数，为避免浮点误差，将每个角度乘以100010001000并四舍五入为整数。则180∘180^\circ180∘对应整数180000180000180000，360∘360^\circ360∘对应360000360000360000。所有角度排序后存储。

计算cic_ici​（小于180∘180^\circ180∘内的点数）

对每个点iii，需快速统计在逆时针方向（即角度增大方向）上，严格小于iii的角度+180∘+180^\circ+180∘的点数。
将排序后的角度复制一份并加上360000360000360000得到双倍数组doubled，其中doubled[i] = angles[i]，doubled[i+n] = angles[i] + 360000。
使用双指针（滑动窗口）：

• 对于每个iii（0≤i<n0 \le i < n0≤i<n），维护右指针ppp，使得doubled[p+1] - angles[i] < 180000。初始p≥ip \ge ip≥i。
• 则ci=p−ic_i = p - ici​=p−i。
• 累加(ci2)\binom{c_i}{2}(2ci​​)到obtuse。

统计对径点对数

利用哈希集合存储所有角度值。遍历每个角度xxx，若x<180000x < 180000x<180000且集合中存在x+180000x+180000x+180000，则计数一次。这样每对恰好被计数一次，无需除以222。

计算答案

根据公式计算并输出。

复杂度分析

• 排序：O(nlog⁡n)O(n\log n)O(nlogn)。
• 双指针滑动：O(n)O(n)O(n)。
• 哈希集合查找：O(n)O(n)O(n)平均。
• 总体时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)，空间复杂度O(n)O(n)O(n)。

代码实现

// Probability Through Experiments// UVa ID: 12535// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.090s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,r,caseNo=1;while(cin>>n>>r&&(n||r)){vector<int>angles(n);for(inti=0;i<n;++i){doubletheta;cin>>theta;angles[i]=(int)(theta*1000.0+0.5);// 转换为整数，避免浮点误差}sort(angles.begin(),angles.end());// 双倍数组，用于滑动窗口统计小于180°的点数vector<int>doubled(2*n);for(inti=0;i<n;++i){doubled[i]=angles[i];doubled[i+n]=angles[i]+360000;}longlongobtuse=0;// 钝角三角形数intp=0;for(inti=0;i<n;++i){if(p<i)p=i;while(p+1<i+n&&doubled[p+1]-angles[i]<180000)++p;longlongcnt=p-i;// 严格小于180°的点数obtuse+=cnt*(cnt-1)/2;}// 统计对径点对数（直径数）unordered_set<int>angSet(angles.begin(),angles.end());longlongdiameterPairs=0;for(intx:angles){if(x<180000&&angSet.count(x+180000))++diameterPairs;}longlongtotal=1LL*n*(n-1)*(n-2)/6;longlongright=diameterPairs*(n-2);// 直角三角形数longlongacute=total-obtuse-right;cout<<"Case "<<caseNo<<": "<<acute<<"\n";++caseNo;}return0;}

总结

本题利用圆内接三角形的几何性质，将问题转化为统计钝角和直角三角形，避免了枚举所有三点组合。关键技巧在于：

• 补集思想：锐角数 = 总数 − 钝角数 − 直角数，简化计数。
• 双指针滑动窗口：高效统计每个点逆时针小于180∘180^\circ180∘的点数，时间复杂度O(n)O(n)O(n)。
• 整数化角度：避免浮点误差，便于精确判断对径关系。
• 哈希集合：快速查找对径点，保证线性时间。

该方法充分利用了排序和哈希，使得n=20000n=20000n=20000时也能在极短时间内完成计算，完美契合题目对高效性的要求。