QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721321 | #9103. Zayin and Fireball | Mu_Silk | TL | 1ms | 4388kb | C++20 | 5.1kb | 2024-11-07 15:50:15 | 2024-11-07 15:50:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double eps=1e-6;
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};
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};
if(sgn(r2.v(m)-l1.v(m))<=0||sgn(r1.v(m)<=l2.v(m))){
f.push_back(l1);
f.push_back(r1);
}
else{
if(sgn(l1.v(m)-l2.v(m))<=0&&sgn(l2.v(m)<=r1.v(m))){
f.push_back(l1);
f.push_back(l2);
}
if(sgn(l1.v(m)-r2.v(m))<=0&&sgn(r2.v(m)<=r1.v(m))){
f.push_back(r2);
f.push_back(r1);
}
}
}
else{
f.push_back(l1);
f.push_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);
}
}
// cout<<l<<" "<<r<<" "<<f.size()<<" "<<ans<<"\n";
}
cout<<fixed<<setprecision(6)<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n=1;
cin>>n;
while(n--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4388kb
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.267454 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 ...