QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667998#9103. Zayin and FireballMu_SilkWA 292ms3864kbC++202.9kb2024-10-23 10:31:432024-10-23 10:31:44

Judging History

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

  • [2024-10-23 10:31:44]
  • 评测
  • 测评结果:WA
  • 用时:292ms
  • 内存:3864kb
  • [2024-10-23 10:31:43]
  • 提交

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 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;
}

mt19937_64 gen(time(NULL));

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<2e-3) {
            uniform_real_distribution<double> dx(x1,x2);
            uniform_real_distribution<double> dy(y1,y2);
            int cnt=0;
            for(int i=0;i<10;i++){
                double x=dx(gen);
                double y=dy(gen);
                int ok=0;
                for(ll i=1;i<=n;i++){
                    ok=max(ok,checkI(x,y,x,y,i));
                }
                if(ok==2)cnt++;
            }
            ans+=(x2-x1)*(y2-y1)/10*cnt;
            continue;
        }
        int ok=0;
        for(ll i=1;i<=n;i++){
            ok=max(ok,checkI(x1,y1,x2,y2,i));
        }
        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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 292ms
memory: 3864kb

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.423271
9.425282
11.167109
3.957599
18.853381
28.274372
36.295384
28.276786
28.276786
28.155550
417.831168
38.215175
125660.509184
125660.561487
125660.618216
125660.548881
31412.779123
39.580420
301.260352
18751.988411
70.911840

result:

wrong answer 2nd numbers differ - expected: '9.42478', found: '9.42327', error = '0.00016'