QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#295606 | #7936. Eliminate Tree | SolitaryDream# | RE | 0ms | 0kb | C++17 | 1.5kb | 2023-12-31 16:28:42 | 2023-12-31 16:28:43 |
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