Uva 4916 Selling Cells(随机算法)
2024-08-30 21:08:24
题意:
给定n个圆的 坐标 和半径, 求第一个圆与其他圆相交的面积占第一个圆的面积的多大。
分析:
如果从局部去想, 处理每个圆之间的关系, 求出他们与第一个圆的交集, 这样可能就会十分复杂了。
不妨从总体去想, 因为答案要求的数字并不是十分精确(保留两位小数), 那么我们可以试试随机算法,
想象在第一个圆内撒绿豆, 那么绿豆肯定会落到第一个圆与其他圆相交的区域, 这时候统计一下撒的绿豆和在区域中的绿豆就可以大概算出这个数字了。
这里有个技巧是用
rand() /(double)(RAND_MAX/'num') 生成 0 ~ num 的浮点数 rand()/(double)RAND_MAX 就是生成一个0 ~ 1的浮点数
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
int n; double x[maxn], y[maxn], r[maxn]; double p2pdis(double x1, double y1, double x2, double y2){
return sqrt((x1-x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
} int main(){
while(scanf("%d", &n) && n){
for(int i = ; i < n; i++){
scanf("%lf %lf %lf", &x[i], &y[i], &r[i]);
}
int time = 2e5;//设置最多循环次数, 在不超时的情况下设置的越大越好
int in = , tot = ;
while(time--){
double tx,ty;
tx = x[] + rand() /(double)(RAND_MAX/ (- * r[])) + r[]; // 令tx在x的半径内随机
ty = y[] + rand() /(double)(RAND_MAX/(- * r[])) + r[]; // 令ty在y的半径内随机
if(p2pdis(tx,ty,x[],y[]) <= r[]){//此时还要判断一下这个点,是否在圆内, 因为我们是在以圆点为中心的正方形内取点
tot++;//判断多少个点符合
for(int i = ; i < n; i++){
if(p2pdis(tx,ty,x[i],y[i]) <= r[i]){
in++;//判断多少个点在小圆内
break;
}
}
}
}
printf("%.2f\n",(double)in/tot);
}
}
最新文章
- java对xml节点属性的增删改查
- IBM Domino 9 出现 Server Controller 未在主机上运行或未在端口2050监听 解决方案
- vim插件ctags的安装和使用
- 【转载】jQuery1.5之后的deferred对象详解
- LeetCode() Repeated DNA Sequences 看的非常的过瘾!
- 详解Python对象属性
- [转]varchar(n),nvarchar(n) 长度、性能、及所占空间分析
- cocos2dx 2.0+ 版本,IOS6.0+设置横屏
- 在Linux里读取UBOOT环境变量
- 【转】ButterKnife的使用--不错
- s3c6410 linux gadget hid驱动
- 一个库搞定各种分享--ShareSDK
- KVM+Qemu+Libvirt实战
- 简易RPC框架-熔断降级机制
- JDBC完成的三个基本工作
- 【ASP.NET MVC系列】浅谈ASP.NET MVC 视图与控制器传递数据
- appium使用错误集合
- CTF中图片隐藏文件分离方法
- 使用putty连接本地VirtualBox上的centos7 linux主机
- IOS常用的第三方开发库