QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620166#9103. Zayin and FireballSiwuTL 375ms3820kbC++172.5kb2024-10-07 16:52:152024-10-07 16:52:16

Judging History

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

  • [2024-10-07 16:52:16]
  • 评测
  • 测评结果:TL
  • 用时:375ms
  • 内存:3820kb
  • [2024-10-07 16:52:15]
  • 提交

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-5){
      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: 375ms
memory: 3820kb

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.425010
9.424979
11.163490
3.958071
18.849769
28.274779
36.295820
28.274548
28.274360
28.156903
417.831760
38.218770
125660.562397
125660.562397
125660.562816
125660.562816
31412.784808
39.578592
301.267697
18751.967440
70.914196

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: