QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620129 | #9103. Zayin and Fireball | Siwu | TL | 2899ms | 3912kb | C++17 | 2.5kb | 2024-10-07 16:44:44 | 2024-10-07 16:44:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct circle{
double x,y,r;
};
double dis2(double x1,double y1,double x2,double y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
ll n;
circle C[509],c[509];
bool p_inner(double x1,double y1,circle &c){
if(dis2(x1,y1,c.x,c.y) <c.r*c.r) return 1;
return 0;
}
bool intersect(double& x1,double& y1,double& x2,double& y2,circle &c){
if(dis2(x1,y1,c.x,c.y)<c.r*c.r)return 1;
if(dis2(x2,y1,c.x,c.y)<c.r*c.r)return 1;
if(dis2(x1,y2,c.x,c.y)<c.r*c.r)return 1;
if(dis2(x2,y2,c.x,c.y)<c.r*c.r)return 1;
if(c.y>=min(y1,y2)&&c.y<=max(y1,y2)){
if(min(abs(c.x-x1),abs(c.x-x2))<c.r) return 1;
}
if(c.x>=min(x1,x2)&&c.x<=max(x1,x2)){
if(min(abs(c.y-y1),abs(c.y-y2))<c.r) return 1;
}
if(c.y>=min(y1,y2)&&c.y<=max(y1,y2)&&c.x>=min(x1,x2)&&c.x<=max(x1,x2)) return 1;
return 0;
}
bool cover(double& x1,double& y1,double& x2,double& y2,circle& c){
if(dis2(x1,y1,c.x,c.y)<=c.r*c.r&&dis2(x2,y1,c.x,c.y)<=c.r*c.r&&dis2(x1,y2,c.x,c.y)<=c.r*c.r&&dis2(x2,y2,c.x,c.y)<=c.r*c.r) return 1;
return 0;
}
int checkI(double &x1,double &y1,double &x2,double &y2,int i){
if(!intersect(x1,y1,x2,y2,C[i])) return 0;
if(cover(x1,y1,x2,y2,c[i])) return 0;
if(intersect(x1,y1,x2,y2,c[i])) return 1;
if(cover(x1,y1,x2,y2,C[i])) return 2;
return 1;
}
void solve(){
cin>>n;
for(ll i=1;i<=n;i++){
cin>>C[i].x>>C[i].y>>C[i].r;
cin>>c[i].x>>c[i].y>>c[i].r;
}
stack<pair<pair<double,double>,double>> q;
q.emplace(make_pair(-1200,-1200),2400);
double ans=0;
while(!q.empty()){
double x1=q.top().first.first,y1=q.top().first.second;
double r=q.top().second;
double x2=x1+r,y2=y1+r;
q.pop();
if(r*r<1e-7){
int ok=0;
for(int i=1;i<=n;i++){
if(p_inner(x1+r/2.0,y1+r/2.0,C[i])&&!p_inner(x1+r/2.0,y1+r/2.0,c[i])){
ok=1;
break;
}
}
if(ok) ans+=r*r;
continue;
}
int ok=0;
for(int i=1;i<=n;i++){
ok=max(ok,checkI(x1,y1,x2,y2,i));
if(ok==2) break;
}
if(ok==0) continue;
if(ok==2){
ans+=r*r;
continue;
}
double midx=(x1+x2)/2.0,midy=(y1+y2)/2.0;
q.emplace(make_pair(x1,y1),r/2.0);
q.emplace(make_pair(x1,midy),r/2.0);
q.emplace(make_pair(midx,midy),r/2.0);
q.emplace(make_pair(midx,y1),r/2.0);
}
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: 2899ms
memory: 3912kb
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.424773 9.424768 11.163293 3.957925 18.849581 28.274355 36.296043 28.274339 28.274334 28.157145 417.831831 38.218836 125660.564471 125660.564471 125660.564708 125660.564708 31412.784959 39.579344 301.267447 18751.965600 70.914260
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 ...