You are given N circles and expected to calculate the area of the union of the circles !

Input

The first line is one integer n indicates the number of the circles. (1 <= n <= 1000)

Then follows n lines every line has three integers

Xi Yi Ri

indicates the coordinate of the center of the circle, and the radius. (|Xi|. |Yi|  <= 1000, Ri <= 1000)

Note that in this problem Ri may be 0 and it just means one point !

Output

The total area that these N circles with 3 digits after decimal point

Example

Input:
3
0 0 1
0 0 1
100 100 1 Output:
6.283

simpson自适应积分法

精度只需要1e-6,十分友好

调试语句懒得删

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-;
const int INF=1e9;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
//
struct cir{
double x,y,r;
friend bool operator < (const cir a,const cir b){return a.r<b.r;}
}c[mxn];int cnt=;
inline double dist(cir a,cir b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
//圆
struct line{
double l,r;
friend bool operator <(const line a,const line b){return a.l<b.l;}
}a[mxn],b[mxn];int lct=;
double f(double x){
int i,j;
lct=;
for(i=;i<=cnt;i++){//计算直线截得圆弧长度
if(fabs(c[i].x-x)>=c[i].r)continue;
double h= sqrt(c[i].r*c[i].r-(c[i].x-x)*(c[i].x-x));
a[++lct].l=c[i].y-h;
a[lct].r=c[i].y+h;
}
if(!lct)return ;
double len=,last=-INF;
sort(a+,a+lct+);
for(i=;i<=lct;i++){//线段长度并
if(a[i].l>last){len+=a[i].r-a[i].l;last=a[i].r;}
else if(a[i].r>last){len+=a[i].r-last;last=a[i].r;}
}
// printf("x:%.3f len:%.3f\n",x,len);
return len;
}
inline double sim(double l,double r){
return (f(l)+*f((l+r)/)+f(r))*(r-l)/;
}
double solve(double l,double r,double S){
double mid=(l+r)/;
double ls=sim(l,mid);
double rs=sim(mid,r);
if(fabs(rs+ls-S)<eps)return ls+rs;
return solve(l,mid,ls)+solve(mid,r,rs);
}
int n;
double ans=;
bool del[mxn];
int main(){
n=read();
int i,j;
double L=INF,R=-INF;
for(i=;i<=n;i++){
c[i].x=read(); c[i].y=read(); c[i].r=read();
// L=min(L,c[i].x-c[i].r);
// R=max(R,c[i].x+c[i].r);
}
//
sort(c+,c+n+);
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
// printf("%d %.3f %.3f %.3f %.3f\n",j,c[j].x,c[i].r,c[j].r,dist(c[i],c[j]));
if(c[j].r-c[i].r>=dist(c[i],c[j]))
{del[i]=;break;}
}
for(i=;i<=n;i++)
if(!del[i])c[++cnt]=c[i];
//删去被包含的圆
// printf("cnt:%d\n",cnt);
double tmp=-INF;int blct=;
for(i=;i<=cnt;i++){
b[++blct].l=c[i].x-c[i].r;
b[blct].r=c[i].x+c[i].r;
}
sort(b+,b+blct+);
// printf("lct:%d\n",blct);
// int tlct=t;
for(i=;i<=blct;i++){
// printf("%.3f %.3f\n",b[i].l,b[i].r);
// printf("tmp:%.3f\n",tmp);
if(b[i].r<=tmp)continue;
L=max(tmp,b[i].l);
// printf("%d: %.3f %.3f\n",i,L,a[i].r);
ans+=solve(L,b[i].r,sim(L,b[i].r));
// printf("ANS:%.3f\n",ans);
// printf("nlct:%d\n",lct);
tmp=b[i].r;
} // ans=solve(L,R,f((L+R)/2));
printf("%.3f\n",ans);
return ;
}

最新文章

  1. C#调用WebService
  2. Spring 定时器的使用
  3. Gitblit中采用Ticket模式进行协作开发
  4. Session的SqlServer模式的配置
  5. ThinkPHP3.2判断手机端访问并设置默认访问模块的方法
  6. P1403约数研究
  7. JavaWeb网页聊天室(WebSocket即时通讯)
  8. 设置将 Microsoft Azure 的网络基础结构以支持设置为灾难恢复站点
  9. mysql 存储引擎MYSIAM和INNODB特性比较
  10. 开始学javascript基础
  11. 依赖注入及AOP简述(十三)——AOP应用举例(完结) .
  12. IZ65534: &#39;JAVA.LANG.CLASSFORMATERROR&#39; ERROR FOR A VALID IDENTIFIER
  13. SendMessage基本认识
  14. Ubuntu下修改DNS重启也能用的方法
  15. HDU 1540 POJ 2892 Tunnel Warfare
  16. MySQL的bigint类型
  17. bzoj 3223: Tyvj 1729 文艺平衡树 (splay)
  18. Java基于opencv实现图像数字识别(二)—基本流程
  19. springcloud Eureka控制台参数说明
  20. Python自学:第二章 注释

热门文章

  1. Java开发小游戏 用键盘控制精灵在游戏中上下左右跑动 窗体小游戏可打包下载,解压后双击start运行
  2. .NET 中,编译器直接支持的数据类型称为基元类型(primitive type).基元类型和.NET框架类型(FCL)中的类型有直接的映射关系.
  3. PCA检测人脸的简单示例_matlab实现
  4. python学习之判断和循环的使用
  5. wdcp 使用说明总结(持续更新中。。。)
  6. Python基础——模块与包
  7. day13-生成器
  8. manjaro kde tim QQ
  9. Applied Nonparametric Statistics-lec6
  10. 前端之bootstrap