QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295606#7936. Eliminate TreeSolitaryDream#RE 0ms0kbC++171.5kb2023-12-31 16:28:422023-12-31 16:28:43

Judging History

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

  • [2023-12-31 16:28:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-31 16:28:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef double db;
struct Point {
    db x,y;
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
    Point operator +(const Point &s) const{
        return {x+s.x,y+s.y};
    }
    Point operator *(const db &s) const{
        return {x*s,y*s};
    }
    db Len() const{
        return hypot(x,y);
    }
};
const int N=1005;
Point a[N],b[N],c[N*N];
bool check(Point p,Point o,db R) {
    return (o-p).Len()<R+1e-9;
}
Point center(Point x,Point y,Point z) {
    db a1=y.x-x.x,b1=y.y-x.y,c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,d=a1*b2-a2*b1;
    return {x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i,1,n) cin >> a[i].x >> a[i].y;
    int m;
    cin >> m;
    FOR(i,1,m) cin >> b[i].x >> b[i].y;
    int K=0;
    FOR(i,1,m) FOR(j,1,n) {
        c[++K]=b[i]-a[j];
    }
    FOR(i,1,K) swap(c[i],c[rand()%K+1]);
    Point o=c[1];
    db R=0;
    FOR(i,2,n) if(!check(c[i],o,R)) {
        o=c[i];
        R=0;
        FOR(j,1,i-1) if(!check(c[j],o,R)) {
            o=(c[i]+c[j])*0.5,R=(o-c[i]).Len();
            FOR(k,1,j-1) if(!check(c[k],o,R)) {
                o=center(c[i],c[j],c[k]);
                R=(o-c[i]).Len();
            }
        }
    }
    cout << R << ' ' << o.x << ' ' << o.y << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2
2 3
3 4
3 5

output:


result: