QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721458#9103. Zayin and FireballMu_SilkTL 1ms4328kbC++205.5kb2024-11-07 16:10:172024-11-07 16:10:18

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 16:10:18]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4328kb
  • [2024-11-07 16:10:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double eps=1e-4;
int sgn(double x){
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}

struct vec{
    double x,y;
    vec operator-(vec a){return {x-a.x,y-a.y};}
    vec operator+(vec a){return {x+a.x,y+a.y};}
    double operator*(vec a){return x*a.x+y*a.y;}
    vec operator*(double a){return {x*a,y*a};}
    vec operator/(double a){return {x/a,y/a};}
    double len(){return sqrt(x*x+y*y);}
    double len2(){return x*x+y*y;}
    vec rot90(){return {-y,x};}
    vec trunc(double l){
        return (*this)/len()*l;
    }
};

double cross(vec a,vec b){
    return a.x*b.y-a.y*b.x;
}

struct seg{
    vec a,b;
};

struct cir{
    vec o;
    double r;
};

struct func{
    double x0,y0,r;
    int sgn;
    int id;
    double value;
    double v(double x){
        return y0+sgn*sqrt(r*r-(x-x0)*(x-x0));
    }
    double s(double l0,double r0){
        vec vl{l0,v(l0)},vr{r0,v(r0)};
        vec dl=vl-vec{x0,y0};
        vec dr=vr-vec{x0,y0};
        double a=acos((dl*dr)/(r*r));

        double s=r*r*a/2-fabs(cross(dl,dr))/2;
        double res=(v(l0)+v(r0))*(r0-l0)/2;
        return res+sgn*s;
    }
};

bool circle_circle_intersection(cir a,cir b,seg& s){
    if(sgn(a.r)==0||sgn(b.r)==0)return false;
    if(sgn(a.o.x-b.o.x)==0&&sgn(a.o.y-b.o.y)==0)return false;

    double d=(a.o-b.o).len();
    if(d>a.r+b.r||d<fabs(a.r-b.r))return false;
    double l=((a.o-b.o).len2()+a.r*a.r-b.r*b.r)/(2*d);
    double h=sqrt(a.r*a.r-l*l);
    vec vl=(b.o-a.o).trunc(l),vh=vec{b.o-a.o}.rot90().trunc(h);
    s=seg{a.o+vl+vh,a.o+vl-vh};
    return true;
}

void solve(){
    int n;cin>>n;
    vector<cir> c1(n),c2(n);
    for(int i=0;i<n;i++){
        cin>>c1[i].o.x>>c1[i].o.y>>c1[i].r;
        cin>>c2[i].o.x>>c2[i].o.y>>c2[i].r;
        c1[i].o.y+=2000;
        c2[i].o.y+=2000;
    }
    vector<double> x;
    for(int i=0;i<n;i++){
        x.push_back(c1[i].o.x-c1[i].r);
        x.push_back(c1[i].o.x+c1[i].r);
        x.push_back(c2[i].o.x-c2[i].r);
        x.push_back(c2[i].o.x+c2[i].r);
        seg s;
        if(circle_circle_intersection(c1[i],c2[i],s)){
            x.push_back(s.a.x);
            x.push_back(s.b.x);
        }
        for(int j=i+1;j<n;j++){
            seg s;
            if(circle_circle_intersection(c1[i],c1[j],s)){
                x.push_back(s.a.x);
                x.push_back(s.b.x);
            }
            if(circle_circle_intersection(c2[i],c2[j],s)){
                x.push_back(s.a.x);
                x.push_back(s.b.x);
            }
            if(circle_circle_intersection(c1[i],c2[j],s)){
                x.push_back(s.a.x);
                x.push_back(s.b.x);
            }
            if(circle_circle_intersection(c2[i],c1[j],s)){
                x.push_back(s.a.x);
                x.push_back(s.b.x);
            }
        }
    }
    // for(auto i:x)cout<<i<<" ";
    // cout<<"\n";
    sort(x.begin(),x.end());    

    double ans=0;
    for(int i=0;i+1<x.size();i++){
        if(sgn(x[i]-x[i+1])==0)continue;
        double l=x[i],r=x[i+1];
        // cout<<l<<" "<<r<<"\n";
        double m=(l+r)/2;
        vector<func> f;
        for(int j=0;j<n;j++){
            if(sgn(l-(c1[j].o.x-c1[j].r))>=0&&sgn(r-(c1[j].o.x+c1[j].r))<=0&&sgn(c1[j].r)>0);
            else continue;

            func l1{c1[j].o.x,c1[j].o.y,c1[j].r,-1,1};
            func r1{c1[j].o.x,c1[j].o.y,c1[j].r, 1,-1};
            l1.value=l1.v(m);
            r1.value=r1.v(m);

            if(sgn(l-(c2[j].o.x-c2[j].r))>=0&&sgn(r-(c2[j].o.x+c2[j].r))<=0&&sgn(c2[j].r)>0){
                func l2{c2[j].o.x,c2[j].o.y,c2[j].r,-1,-1};
                func r2{c2[j].o.x,c2[j].o.y,c2[j].r, 1,1};
                l2.value=l2.v(m);
                r2.value=r2.v(m);

                if(sgn(r2.value-l1.value)<=0||sgn(r1.value<=l2.value)){
                    f.emplace_back(l1);
                    f.emplace_back(r1);
                }
                else{
                    if(sgn(l1.value-l2.value)<=0&&sgn(l2.value<=r1.value)){
                        f.emplace_back(l1);
                        f.emplace_back(l2);
                    }
                    if(sgn(l1.value-r2.value)<=0&&sgn(r2.value<=r1.value)){
                        f.emplace_back(r2);
                        f.emplace_back(r1);
                    }
                }
            }
            else{
                f.emplace_back(l1);
                f.emplace_back(r1);
            }
        }
        for(int i=0;i<f.size();i++)f[i].value=f[i].v(m);
        sort(f.begin(),f.end(),[&](func a,func b){
            if(sgn(a.value-b.value)==0)return a.id>b.id;
            return a.value<b.value;
        });
        // cout<<x[i]<<" "<<x[i+1]<<"\n";
        // cout<<f.size()<<"\n";
        int cnt=0;
        for(int i=0;i+1<f.size();i++){
            if(f[i].id>0)cnt++;
            else cnt--;
            if(cnt>0){
                ans+=f[i+1].s(l,r)-f[i].s(l,r);
            }
        }
        // if(isnan(ans)){
        //     cout<<fixed<<setprecision(6)<<l<<" "<<r<<" "<<f.size()<<" "<<ans<<"\n";
        //     exit(0);
        // }
    }
    cout<<fixed<<setprecision(6)<<ans<<"\n";
}

int main(){
    // double st=clock();
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    cin>>n;
    while(n--)solve();
    // double ed=clock();
    // cout<<(ed-st)/1000<<"ms\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4328kb

input:

22
1
0 0 1 0 0 1
1
0 0 2 0 0 1
1
0 0 2 1 0 1
1
0 0 2 2 0 1
1
0 0 2 1 0 2
2
0 0 1 0 0 0
0 0 3 0 0 2
2
0 0 1 0 0 0
0 0 3 0 0 1
2
-233 0 3 -234 0 1
233 0 2 231 0 1
2
0 0 1 0 0 0
1 0 3 0 0 1
2
0 0 1 0 0 0
0 2 3 0 0 1
2
2 4 2 2 4 1
3 3 3 3 3 1
4
0 1 1 0 2 2
3 3 3 3 4 2
250 2 4 0 0 100
255 7 12 254 10 4
3...

output:

0.000000
9.424778
9.424778
11.163304
3.957934
18.849556
28.274334
36.296045
28.274334
28.274334
28.157137
417.831823
38.218848
125660.564551
125660.564551
125660.564789
125660.564789
31412.784943
39.579337
301.265752
18751.965611
70.914255

result:

ok 22 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

30
500
129 442 8 147 446 7
131 405 28 110 416 4
164 446 3 146 456 0
166 453 20 152 423 24
100 417 25 164 439 5
119 425 7 115 420 19
127 408 5 107 423 18
157 449 18 148 444 16
178 392 10 134 456 27
162 419 25 124 456 15
133 425 6 119 444 16
132 412 5 127 464 28
139 373 19 148 414 9
114 425 2 117 431 ...

output:


result: