新闻详情

新闻详情

首页 / 资讯中心 / 详情

UVa 12535 Probability Through Experiments

发布时间:2026/10/1 2:29:28来源:尧图网络
UVa 12535 Probability Through Experiments
题目描述在圆边界上随机取三个点它们构成锐角三角形的概率为0.250.250.25。教授Neal Wu\texttt{Neal Wu}Neal Wu希望通过实验验证该结果。传统方法需重复实验极多次如101810^{18}1018次耗时过长。他发现可以一次性生成nnn个点利用所有三点组合共Nn(n−1)(n−2)6N \frac{n(n-1)(n-2)}{6}N6n(n−1)(n−2)​个三角形统计锐角三角形个数MMM则概率即为M/NM/NM/N。给定圆上的nnn个点以角度给出请计算锐角三角形数量。输入格式输入包含约404040个测试用例。每个用例以两个正整数nnn0n≤200000 n \le 200000n≤20000和rrr0r≤5000 r \le 5000r≤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\gamma360^\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则直角三角形数RD×(n−2)R D \times (n-2)RD×(n−2)。对径点两角度之差恰好为180∘180^\circ180∘对应整数表示下差值为180000180000180000。因此锐角数AT−O−RA T - O - RAT−O−R其中Tn(n−1)(n−2)6T \frac{n(n-1)(n-2)}6T6n(n−1)(n−2)​。解题思路角度处理输入角度为三位小数为避免浮点误差将每个角度乘以100010001000并四舍五入为整数。则180∘180^\circ180∘对应整数180000180000180000360∘360^\circ360∘对应360000360000360000。所有角度排序后存储。计算cic_ici​小于180∘180^\circ180∘内的点数对每个点iii需快速统计在逆时针方向即角度增大方向上严格小于iii的角度180∘180^\circ180∘的点数。将排序后的角度复制一份并加上360000360000360000得到双倍数组doubled其中doubled[i] angles[i]doubled[in] angles[i] 360000。使用双指针滑动窗口对于每个iii0≤in0 \le i n0≤in维护右指针ppp使得doubled[p1] - angles[i] 180000。初始p≥ip \ge ip≥i。则cip−ic_i p - ici​p−i。累加(ci2)\binom{c_i}{2}(2ci​​)到obtuse。统计对径点对数利用哈希集合存储所有角度值。遍历每个角度xxx若x180000x 180000x180000且集合中存在x180000x180000x180000则计数一次。这样每对恰好被计数一次无需除以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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,r,caseNo1;while(cinnr(n||r)){vectorintangles(n);for(inti0;in;i){doubletheta;cintheta;angles[i](int)(theta*1000.00.5);// 转换为整数避免浮点误差}sort(angles.begin(),angles.end());// 双倍数组用于滑动窗口统计小于180°的点数vectorintdoubled(2*n);for(inti0;in;i){doubled[i]angles[i];doubled[in]angles[i]360000;}longlongobtuse0;// 钝角三角形数intp0;for(inti0;in;i){if(pi)pi;while(p1indoubled[p1]-angles[i]180000)p;longlongcntp-i;// 严格小于180°的点数obtusecnt*(cnt-1)/2;}// 统计对径点对数直径数unordered_setintangSet(angles.begin(),angles.end());longlongdiameterPairs0;for(intx:angles){if(x180000angSet.count(x180000))diameterPairs;}longlongtotal1LL*n*(n-1)*(n-2)/6;longlongrightdiameterPairs*(n-2);// 直角三角形数longlongacutetotal-obtuse-right;coutCase caseNo: acute\n;caseNo;}return0;}总结本题利用圆内接三角形的几何性质将问题转化为统计钝角和直角三角形避免了枚举所有三点组合。关键技巧在于补集思想锐角数 总数 − 钝角数 − 直角数简化计数。双指针滑动窗口高效统计每个点逆时针小于180∘180^\circ180∘的点数时间复杂度O(n)O(n)O(n)。整数化角度避免浮点误差便于精确判断对径关系。哈希集合快速查找对径点保证线性时间。该方法充分利用了排序和哈希使得n20000n20000n20000时也能在极短时间内完成计算完美契合题目对高效性的要求。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

OpenHarmony 五种截屏方式与避坑指南 2026/10/1 6:17:51

OpenHarmony 五种截屏方式与避坑指南

hdc shell snapshot_display这个命令,我第一次在 OpenHarmony 开发板上敲的时候,返回了一句 usage,当时还以为工具没编进去。后来翻了图形子系统的源码才发现,参数写法和我想的不一样。这件事让我意识到,OpenHarmony 的…

阅读更多 →
OpenHarmony截屏五种方式:三种粒度选型与权限避坑 2026/10/1 6:17:51

OpenHarmony截屏五种方式:三种粒度选型与权限避坑

上周在群里被问到一个挺典型的问题:OpenHarmony 设备上想弄一张屏幕截图,除了老老实实按电源键加音量减,还有没有别的路子?问的人不是普通用户,是个正在做行业定制的开发,他的真实诉求是"我要在自动化…

阅读更多 →
Android网络视频播放器源码拆解:ExoPlayer缓存与缓冲策略实战 2026/10/1 6:17:51

Android网络视频播放器源码拆解:ExoPlayer缓存与缓冲策略实战

简介:这是一份基于安卓的网络视频播放器完整源码项目,定位为毕业设计参考与安卓进阶练习,覆盖网络视频解析、播放控制、进度同步、全屏切换等典型功能。项目源码以Java实现为主,涉及网络通信、异步任务和界面布局,适合…

阅读更多 →
从零搭建AI工程体系:数据、训练、部署、监控全链路实战 2026/10/1 6:17:51

从零搭建AI工程体系:数据、训练、部署、监控全链路实战

我带了几年做AI应用落地的团队,面试过不少算法背景的候选人,发现一个特别普遍的现象:让他在notebook里跑一个模型,准确率能聊得头头是道,损失曲线怎么分析也门儿清,但只要一问"这个模型上线后用户请求…

阅读更多 →
2025五一杯A题支路车流量推测:守恒建模与Python实现 2026/10/1 6:17:50

2025五一杯A题支路车流量推测:守恒建模与Python实现

简介:面向2025年五一杯数学建模A题“支路车流量推测问题”的参赛团队,这套完整资源包提供从解题思路到最终成果的一站式内容:完整成品论文、Python与MATLAB双版本代码、全部结果表格,以及思路解析。压缩包共54个文件,体…

阅读更多 →
Windows用winget更新PowerShell 7:一行命令与版本区分 2026/10/1 6:17:44

Windows用winget更新PowerShell 7:一行命令与版本区分

如果你手上有一台 Windows,想给 PowerShell 更新一下,最省事的做法真的就是一行命令:winget install --id Microsoft.PowerShell --source winget。敲下去,等进度条走完,关掉窗口重开,$PSVersionTable里的版…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉