QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574672 | #9103. Zayin and Fireball | quailty | AC ✓ | 7249ms | 4392kb | C++20 | 5.3kb | 2024-09-18 23:43:35 | 2024-09-23 15:04:26 |
Judging History
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