BZOJ
题意:给出\(n(n<=1000)\)个圆,每个圆给出圆心坐标\((x,y)\)和半径\(r\),求它们的面积并。
方法一:辛普森积分
本题用辛普森积分,精度eps开小会T一个点,开大会WA一个点;如果用上文中提到的自适应辛普森就会T很多点,因此这种方法时间复杂度不明确,取决于精度和数据强度。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const int N = 1e3 + 5;
const int M = 1e5 + 5;
const double eps=1e-8;
int n,bj[N];
struct Cir{int x,y,r;}p[N];
struct Line{double l,r;}S[N];
inline bool cmp_Cir(Cir a,Cir b){
return a.r<b.r;
}
inline bool cmp_Line(Line a,Line b){
return a.l<b.l;
}
inline int cmp(double x){
if (x<=eps&&x>=-eps) return 0;
return (x>0)?1:-1;
}
inline double Sqr(double x){return x*x;}
inline double f(double x){
int top=0;
for(int i=1;i<=n;++i)
if(p[i].x-p[i].r<=x&&x<=p[i].x+p[i].r){
double len=sqrt(Sqr(p[i].r)-Sqr(fabs(p[i].x-x)));
S[++top]=(Line){p[i].y-len,p[i].y+len};
}
sort(S+1,S+top+1,cmp_Line);
double ret=0,l=-1e9,r=-1e9;
for(int i=1;i<=top;++i)
if(S[i].l-r>eps)ret+=r-l,l=S[i].l,r=S[i].r;
else if(S[i].r-r>eps)r=S[i].r;
return ret+r-l;
}
inline double Simpson(double l,double r){return (r-l)*(f(l)+f(r)+4.0*f((l+r)/2.0))/6.0;}
inline double asr(double l,double r,double val){
double mid=(l+r)/2.0;
double lval=Simpson(l,mid),rval=Simpson(mid,r);
if(cmp(lval+rval-val)==0){return val;}
else return asr(l,mid,lval)+asr(mid,r,rval);
}
int main(){
n=read();
for(int i=1;i<=n;++i){
p[i].x=read();
p[i].y=read();
p[i].r=read();
}
int l=1e9,r=-1e9;
for(int i=1;i<=n;++i)l=min(l,p[i].x-p[i].r);
for(int i=1;i<=n;++i)r=max(r,p[i].x+p[i].r);
sort(p+1,p+n+1,cmp_Cir);
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j){
if (cmp(sqrt(Sqr(p[i].x-p[j].x)+Sqr(p[i].y-p[j].y))+p[i].r-p[j].r)<=0){
bj[i]=1;
break;
}
}
int m=0;
for(int i=1;i<=n;++i)if(!bj[i])p[++m]=p[i];
n=m;
double ans=asr(l*1.0,r*1.0,Simpson(l,r));
printf("%.3lf\n",ans);
return 0;
}
方法二:格林公式
难得高数微积分知识还能派上用场,时间复杂度\(O(n^2logn)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n;
const int N=1005;
const double Pi=acos(-1.0);
struct Point{
int x,y;
inline Point(){}
inline Point(int xx,int yy):x(xx),y(yy){}
inline Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}
inline Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}
inline bool operator <(const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
inline bool operator ==(const Point &b)const{return x==b.x&&y==b.y;}
};
struct Cir{
Point p;int r;
inline bool operator <(const Cir &b)const{return p<b.p||p==b.p&&r<b.r;}
inline bool operator ==(const Cir &b)const{return p==b.p&&r==b.r;}
}c[N];
pair<double,int>st[N<<1];
inline double calc(double r,double x,double y,double t1,double t2){
return r*(r*(t2-t1)+x*(sin(t2)-sin(t1))-y*(cos(t2)-cos(t1)));
}
double solve(int id){
int top=0,cnt=0;
for(int i=1;i<=n;++i){
if(i!=id){
double dis=sqrt((c[i].p.x-c[id].p.x)*(c[i].p.x-c[id].p.x)+(c[i].p.y-c[id].p.y)*(c[i].p.y-c[id].p.y));
if(c[id].r+dis<=c[i].r)return 0;
if(c[i].r+dis<=c[id].r||c[i].r+c[id].r<=dis)continue;
double del=acos((c[id].r*c[id].r+dis*dis-c[i].r*c[i].r)/(2*c[id].r*dis));
double ang=atan2(c[i].p.y-c[id].p.y,c[i].p.x-c[id].p.x);
double l=ang-del,r=ang+del;
if(l<-Pi)l+=2*Pi;if(r>=Pi)r-=2*Pi;
if(l>r)++cnt;
st[++top]=make_pair(l,1),st[++top]=make_pair(r,-1);
}
}
st[0]=make_pair(-Pi,0),st[++top]=make_pair(Pi,0);
sort(st+1,st+1+top);
double res=0;
for(int i=1;i<=top;cnt+=st[i++].second)
if(!cnt)res+=calc(c[id].r,c[id].p.x,c[id].p.y,st[i-1].first,st[i].first);
return res;
}
int main(){
n=read();
for(int i=1;i<=n;++i){
c[i].p.x=read();
c[i].p.y=read();
c[i].r=read();
}
sort(c+1,c+1+n);
n=unique(c+1,c+1+n)-c-1;
double ans=0;
for(int i=1;i<=n;++i)ans+=solve(i);
printf("%.3lf\n",ans*0.5);
return 0;
}
标签:ch,return,int,double,面积,st,inline,模板
From: https://www.cnblogs.com/PPXppx/p/16860951.html