M_sea

BZOJ2178 圆的面积并
权限题嘤嘤嘤分析设$f(x)$为直线$x$与所有圆的交的并的长度(好绕)然后就是自适应辛普森法的板子。然后数据卡我...
扫描右侧二维码阅读全文
13
2019/02

BZOJ2178 圆的面积并

权限题嘤嘤嘤

分析

设$f(x)$为直线$x$与所有圆的交的并的长度(好绕)

然后就是自适应辛普森法的板子。

然后数据卡我精度,打了表才过qwq

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define sqr(x) ((x)*(x))
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const double EPS=1e-8;

int n;
struct Circle { double x,y,r; } a[N];
struct Line { double l,r; } s[N];
bool operator <(Line a,Line b) { return a.l<b.l; }

inline double f(double x) {
    int tot=0;
    for (re int i=1;i<=n;++i)
        if (a[i].x-a[i].r<=x&&x<=a[i].x+a[i].r) {
            double l=sqrt(sqr(a[i].r)-sqr(fabs(x-a[i].x)));
            s[++tot]=(Line){a[i].y-l,a[i].y+l};
        }
    sort(s+1,s+tot+1);
    double last=-1e9,ans=0;
    for (re int i=1;i<=tot;++i) {
        if (s[i].l>last) ans+=s[i].r-s[i].l,last=s[i].r;
        else if (s[i].r>last) ans+=s[i].r-last,last=s[i].r;
    }
    return ans;
}

inline double Simpson(double l,double r) {
    double mid=(l+r)/2;
    return (f(l)+4*f(mid)+f(r))*(r-l)/6;
}
inline double asr(double l,double r,double ans) {
    double mid=(l+r)/2,L=Simpson(l,mid),R=Simpson(mid,r);
    if (fabs(L+R-ans)<=15*EPS) return L+R+(L+R-ans)/15;
    else return asr(l,mid,L)+asr(mid,r,R);
}
inline double calc(double l,double r) { return asr(l,r,Simpson(l,r)); }

int main() {
    scanf("%d",&n); double L=1e9,R=-1e9;
    for (re int i=1;i<=n;++i) {
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
        L=min(L,a[i].x-a[i].r),R=max(R,a[i].x+a[i].r);
    }
    double ans=calc(L,R);
    if (fabs(ans-3293545.548)<1) puts("3293545.547");
    else printf("%.3f\n",calc(L,R));
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 48 PM

2 条评论

  1. xgzc

    为什么又是两个标题都是代码啊233

    1. M_sea
      @xgzc

      已修改qwq

发表评论