圆的面积并

题意:

给出N个圆,求其面积并,所有圆的坐标和半径均小于1000…

分析:

这道题,计算几何稳稳地过,但是代码长,加我不会…
然后我们使用,辛普森积分,来近似求出面积…
我们先处理掉那些内切和内含的圆,然后使用辛普森积分公式

S=\frac{r-l}{6}\times \Big(f(l)+f(\frac{l+r}{2})+f(r)\Big)

我们把所有圆看成是面包,把他们紧紧压在x轴上,就得到了一个类似波浪的不规则面积….
我们使用递归的做法当把一段求完积分后,和从中截断分成两端求的差太大时,我们就分开求,知道精度够了为止….
然后这道题目,直接辛普森积分的大多T了,我们还要加一些优化,比如记忆化什么的,然后zzd神仙表示,这样精度还不够的化我们可以预先把有面积的段分成好多块分开求,最后加起来….
我表示我代码好菜,还要加卡常头文件…

代码:

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define db double
#define fi first
#define se second
const LL N=1e3+10;
const LL mod=12345678;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,vis[N];
db maxn=-2000,minn=2000;
struct Node{db x,y,r;}node[N];
void qu(int a,int b)
{
    if(node[a].r<node[b].r) swap(a,b);
    db S=sqrt(1.0*(node[a].x-node[b].x)*(node[a].x-node[b].x)+1.0*(node[a].y-node[b].y)*(node[a].y-node[b].y));
    if(S<=node[a].r-node[b].r) vis[b]=1;
}
db my_max(db a,db b){return a>b?a:b;}
db my_min(db a,db b){return a<b?a:b;}
bool cmp(Node a,Node b) {return a.x+a.r<b.x+b.r;}
db f(db a)
{
    db ret=0,r=-2000;int siz=0;
    pair<db,db> lr[N];
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        db s=node[i].x-a;
        if(s<0) s=-s;
        if(s>node[i].r) continue;
        db flag=node[i].r*node[i].r-s*s;flag=sqrt(flag);
        lr[++siz].fi=node[i].y-flag,lr[siz].se=node[i].y+flag;
    }
    sort(lr+1,lr+siz+1);
    for(int i=1;i<=siz;i++)
    {
        if(lr[i].fi>r) ret+=lr[i].se-lr[i].fi;
        else if(lr[i].se>r) ret+=lr[i].se-r;
        r=my_max(lr[i].se,r);
    }
    return ret;
}
db simpson(db l,db r) {return (r-l)*(f(l)+4*f((l+r)/2)+f(r))/6.0;}
db solve(db l,db r,db mdzz)
{   
    db mid=(l+r)/2;
    db now_ans=(mdzz!=0?mdzz:simpson(l,r));
    db ll=simpson(l,mid),rr=simpson(mid,r);
    if(abs(now_ans-ll-rr)<=eps) return now_ans;
    return solve(l,mid,ll)+solve(mid,r,rr);
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&node[i].x,&node[i].y,&node[i].r);
        maxn=my_max(maxn,node[i].x+node[i].r);
        minn=my_min(minn,node[i].x-node[i].r);
    }
    sort(node+1,node+n+1,cmp);
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) qu(i,j);
    db ans=0;
    for(int i=minn;i<maxn;i++)
    {
        if(f(i)==0&&f(i+1)==0) continue;
        ans+=solve(i,i+1,0);
    }
    printf("%.3lf",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注