在排除商店的中心不在雨伞范围内,排除伞在商店内而面积达不到一半时。
面雨伞覆盖了整个商店是可行的,最后剩一种相交的情况,求圆面积的并。
//之前不怎么敢用三角函数怕丢失精度,没想是可以的。
代码如下 :
#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
#define inf 1e8
#define maxn 100
#define PI acos(-1.0)
struct point {double x,y;};
struct circle{point cen;double r;}cir[maxn];
int id;double minr;
int n;
bool zero(double x){return x>0? x<eps :x>-eps;}
double min(double a,double b){return a>b? b:a;}
double distance(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool judge(double rr)
{
int i;
for(i=0;i<n;i++)
{
double dis=distance(cir[id].cen,cir[i].cen);
if(rr-dis< eps)return false;//
if(rr-dis-cir[i].r>=0)continue;//c?úo?,?ú?Da
double a=cir[i].r*cir[i].r*PI;
double c=rr*rr*PI;
if(dis+rr-cir[i].r<-eps)//a?úo?c
{
if(c-a/2> -eps)continue;
else return false;
}
double l=(rr+dis+cir[i].r)/2;
double area1=2*sqrt(l*(l-rr)*(l-dis)*(l-cir[i].r));
double anga=acos((cir[i].r*cir[i].r+dis*dis-rr*rr)/(2*dis*cir[i].r));
double angc=acos((dis*dis+rr*rr-cir[i].r*cir[i].r)/(2*dis*rr));
double res=anga/(PI)*a+angc/(PI)*c-area1;
if(res-a/2<0)return false;
}
return true;
}
double two(double l,double r)
{
double mid=(l+r)/2.0;
if(zero(r-l))return mid;
if(judge(mid))
return two(l,mid);
else return two(mid,r);
}
int main()
{
int t ;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf",&cir[i].cen.x,&cir[i].cen.y,&cir[i].r);
}
double minn=inf;
for(i=0;i<n;i++)
{
id=i;
minn=min(minn,two(0,inf));
}
printf("%.4lf\n",minn);
}
return 0;
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭电ACM2000-2099题的解题报告
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
这份压缩爆内包含了2019年杭电多校第二场的数据与标程,欢迎下载
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =