2178: 圆的面积并
Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 1740 Solved: 450
[Submit][Status][Discuss]
Description
给出N个圆，求其面积并
Input
先给一个数字N ,N< = 1000 接下来是N行是圆的圆心，半径，其绝对值均为小于1000的整数
Output
面积并，保留三位小数
太可怕了！！！！！！
直接上辛普森积分 函数值就是x=..线上的区间并
区间并直接排序扫描就可以了
Xcode太愚蠢了样例那么大貌似把控制台崩掉了
不停的T啊....最后发现是辛普森积分写丑了......
结果我写的可能还是太丑了，超过10s.....那些快的都没用辛普森积分吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=,INF=1e9;
const double eps=1e-;
inline int sgn(double x){
if(abs(x)<eps) return ;
else return x<?-:;
}
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n;
struct Interval{
double l,r;
bool operator <(const Interval &a) const{
return l==a.l?r<a.r:l<a.l;
}
Interval(double a=,double b=):l(a),r(b){}
}a[N],b[N]; struct Circle{
int x,y,r;
Circle(){}
Circle(int x,int y,int r):x(x),y(y),r(r){}
Interval f(double p){
double dx=x-p,t=sqrt(r*r-dx*dx);
return Interval(y-t,y+t);
}
}C[N];
double Dis(Circle a,Circle b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool del[N];
void iniCircle(){
for(int i=;i<=n;i++) if(!del[i])
for(int j=i+;j<=n;j++) if(!del[j])
if(Dis(C[i],C[j])<=abs(C[i].r-C[j].r)){
if(C[i].r>C[j].r) del[j]=;
else del[i]=;
}
int p=;
for(int i=;i<=n;i++) if(!del[i]) C[++p]=C[i];
n=p;
}
inline double F(double x){
int m=;
for(int i=;i<=n;i++)
if(C[i].x-C[i].r<=x&&x<=C[i].x+C[i].r) a[++m]=C[i].f(x);
sort(a+,a++m);
double last=-INF,re=;
for(int i=;i<=m;i++){
if(a[i].l>last) re+=a[i].r-a[i].l,last=a[i].r;
else if(a[i].r>last) re+=a[i].r-last,last=a[i].r;
}
return re;
} inline double cal(double l,double r){
return (F(l)+F(r)+*F((l+r)/))*(r-l)/;
}
inline double cal(double l,double r,double fl,double fr,double fm){
return (fl+fr+*fm)*(r-l)/;
}
double Simpson(double l,double r,double now,double fl,double fr,double fm){
double mid=(l+r)/,flm=F((l+mid)/),frm=F((mid+r)/);
double p=cal(l,mid,fl,fm,flm),q=cal(mid,r,fm,fr,frm);
if(sgn(now-p-q)==) return now;
else return Simpson(l,mid,p,fl,fm,flm)+Simpson(mid,r,q,fm,fr,frm);
} double lb=INF,rb=-INF;
int main(int argc, const char * argv[]) {
n=read();
for(int i=;i<=n;i++){//printf("i %d\n",i);
C[i].x=read();C[i].y=read();C[i].r=read();
lb=min(lb,(double)C[i].x-C[i].r);
rb=max(rb,(double)C[i].x+C[i].r);
}
iniCircle();
//printf("%d\n",n);
double fl=F(lb),fr=F(rb),fm=F((lb+rb)/);
printf("%.3lf",Simpson(lb,rb,cal(lb,rb,fl,fr,fm),fl,fr,fm));
return ;
}