QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#574672#9103. Zayin and FireballquailtyAC ✓7249ms4392kbC++205.3kb2024-09-18 23:43:352024-09-23 15:04:26

Judging History

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

  • [2024-09-23 15:04:26]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:7249ms
  • 内存:4392kb
  • [2024-09-18 23:43:36]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4356kb
  • [2024-09-18 23:43:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int MAXN=505;
const db eps=1e-9;
const db pi=acos(-1.0);
int sgn(db x)
{
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}
struct Point
{
    db x,y;
    Point() {}
    Point(db _x,db _y):x(_x),y(_y) {}
    Point operator + (const Point& t)const { return Point(x+t.x,y+t.y); }
    Point operator - (const Point& t)const { return Point(x-t.x,y-t.y); }
    Point operator * (const db& t)const { return Point(x*t,y*t); }
    Point operator / (const db& t)const { return Point(x/t,y/t); }
    db operator * (const Point& t)const { return x*t.y-y*t.x; }
    db operator ^ (const Point& t)const { return x*t.x+y*t.y; }
    bool operator == (const Point& t)const { return sgn(x-t.x)==0 && sgn(y-t.y)==0; }
    bool operator != (const Point& t)const { return !((*this)==t); }
    db len()const { return sqrt(x*x+y*y); }
    Point norm()const { return *this/len(); }
    Point rot90()const { return Point(-y,x); }
};
struct Circle
{
    Point o;
    db r;
    Circle() {}
    Circle(Point _o,db _r):o(_o),r(_r) {}
    bool operator == (const Circle& t)const
    {
        return o==t.o && sgn(r-t.r)==0;
    }
    int intersect(const Circle& t,Point& p1,Point& p2)const
    {
        db d=(o-t.o).len();
        if(sgn(d)==0)return -1;
        if(sgn(d-abs(r-t.r))<0)return 0;
        if(sgn(d-(r+t.r))>0)return 0;
        db c=(r*r+d*d-t.r*t.r)/(2*d);
        Point v=(t.o-o).norm(),m=o+v*c;
        db h=sqrt(max<db>(0,r*r-c*c));
        if(sgn(h)==0)
        {
            p1=p2=m;
            return 1;
        }
        v=v.rot90();
        p1=m-v*h,p2=m+v*h;
        return 2;
    }
    db angle(const Point& t)const
    {
        db r=atan2(t.y-o.y,t.x-o.x);
        return r<0 ? r+2*pi : r;
    }
    Point point(const db& ang)const
    {
        return o+Point(cos(ang),sin(ang))*r;
    }
} outer[MAXN],inner[MAXN];
void range_diff(vector<pair<db,db>>& outer,const vector<pair<db,db>>& inner)
{
    for(auto& [l,r] : inner)
    {
        vector<pair<db,db>> tmp;
        for(auto& [tl,tr] : outer)
        {
            if(sgn(tl-l)<0 && sgn(tr-r)>0)
            {
                tmp.emplace_back(tl,l);
                tmp.emplace_back(r,tr);
            }
            else if(sgn(tl-l)<0)
                tmp.emplace_back(tl,min(tr,l));
            else if(sgn(tr-r)>0)
                tmp.emplace_back(max(tl,r),tr);
        }
        outer.swap(tmp);
    }
}
void get_range(int i,int ti,int j,int tj,vector<pair<db,db>>& range)
{
    const Circle& ci=(ti ? outer[i] : inner[i]);
    const Circle& cj=(tj ? outer[j] : inner[j]);
    db d=(ci.o-cj.o).len();
    if(sgn(d-(ci.r+cj.r))>=0)return;
    if(sgn(d-(cj.r-ci.r))<=0)
    {
        if(sgn(d-(cj.r-ci.r))<0 || sgn(d)!=0 || !ti)
            range.emplace_back(0,2*pi);
        return;
    }
    if(sgn(d-(ci.r-cj.r))<=0)return;
    Point p1(0,0),p2(0,0);
    assert(ci.intersect(cj,p1,p2)==2);
    db l=ci.angle(p1),r=ci.angle(p2);
    if(l<=r)range.emplace_back(l,r);
    else range.emplace_back(l,2*pi),range.emplace_back(0,r);
}
db clamp(db x,const pair<db,db>& range)
{
    return min(range.second,max(range.first,x));
}
db cal(int n,int i,int ti,const pair<db,db>& range)
{
    vector<pair<db,db>> event;
    for(int j=0; j<n; j++)
    {
        if(j==i)continue;
        vector<pair<db,db>> outer_range,inner_range;
        get_range(i,ti,j,1,outer_range);
        get_range(i,ti,j,0,inner_range);
        range_diff(outer_range,inner_range);
        for(auto& [l,r] : outer_range)
        {
            event.emplace_back(clamp(l,range),1);
            event.emplace_back(clamp(r,range),-1);
        }
    }
    sort(event.begin(),event.end());
    const Circle& c=(ti ? outer[i] : inner[i]);
    auto cal=[&](db l,db r)
    {
        return c.r*c.r*((r-l)-sin(r-l))+c.point(l)*c.point(r);
    };
    db res=cal(range.first,range.second),la;
    int cnt=0;
    for(auto& [v,ty] : event)
    {
        if(cnt>0)res-=cal(la,v);
        cnt+=ty,la=v;
    }
    return res/2;
}
int solve()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%Lf%Lf%Lf",&outer[i].o.x,&outer[i].o.y,&outer[i].r);
        scanf("%Lf%Lf%Lf",&inner[i].o.x,&inner[i].o.y,&inner[i].r);
    }
    db res=0;
    for(int i=0; i<n; i++)
    {
        db d=(outer[i].o-inner[i].o).len();
        if(sgn(d-(inner[i].r-outer[i].r))<=0)continue;
        if(sgn(d-(inner[i].r+outer[i].r))>=0)
        {
            res+=cal(n,i,1, {0,2*pi});
            continue;
        }
        if(sgn(d-(outer[i].r-inner[i].r))<=0)
        {
            res+=cal(n,i,1, {0,2*pi});
            res-=cal(n,i,0, {0,2*pi});
            continue;
        }
        Point p1(0,0),p2(0,0);
        assert(outer[i].intersect(inner[i],p1,p2)==2);
        db l=outer[i].angle(p1),r=outer[i].angle(p2);
        if(l<=r)res+=cal(n,i,1, {0,l})+cal(n,i,1, {r,2*pi});
        else res+=cal(n,i,1, {r,l});
        l=inner[i].angle(p2),r=inner[i].angle(p1);
        if(l<=r)res-=cal(n,i,0, {l,r});
        else res-=cal(n,i,0, {l,2*pi})+cal(n,i,0, {0,r});
    }
    return 0*printf("%.12Lf\n",res);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.000000000000
9.424777960769
9.424777960769
11.163304174673
3.957933714240
18.849555921539
28.274333882308
36.296045403392
28.274333882308
28.274333882308
28.157136736100
417.831822927442
38.218847751557
125660.564550938135
125660.564550938135
125660.564788922310
125660.564788922310
31412.784943244...

result:

ok 22 numbers

Test #2:

score: 0
Accepted
time: 7249ms
memory: 4392kb

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:

16325.897818541519
3633664.465840674049
213359.268322280049
222590.371031198215
215595.956054738800
233363.113815076860
3014984.870781688245
16169.051247618530
3524934.377027256872
226126.671102566986
219815.065402863833
215704.473090403862
241176.720627714100
2912302.913357378232
16386.416990298520...

result:

ok 30 numbers