HDU 6242

题意略。

思路：这个题的思路非常诡异。由于题目保证存在这样一个圆，那么每个点在这个圆上的概率是1/2，我任选3个点，这3个点都在这个圆上的概率是1 / 8。

不都在这个圆上的概率是7 / 8，在这样选取30次后，还没有找到这个圆的概率是0.018，根据这个条件我们可以暴力验证。

详见代码：

#include<bits/stdc++.h>
#define maxn 100005
#define eps 1e-6
using namespace std;

struct Point{
    double x,y;
    Point(double a = 0,double b = 0){
        x = a,y = b;
    }
};

Point store[maxn];
int T,n;

Point circumcenter(Point a,Point b,Point c){
    double a1 = b.x - a.x,b1 = b.y - a.y,c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x,b2 = c.y - a.y,c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    return Point(a.x + (c1 * b2 - c2 * b1) / d,a.y + (a1 * c2 - a2 * c1) / d);
}
double dist(Point p1,Point p2){
    double dx = p1.x - p2.x,dy= p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}
int sgn(double x,double y){
    if(fabs(x - y) < eps) return 0;
    else if(x + eps < y) return -1;
    else return 1;
}

int main(){
    scanf("%d",&T);
    srand(time(0));
    while(T--){
        scanf("%d",&n);
        for(int i = 0;i < n;++i){
            scanf("%lf%lf",&store[i].x,&store[i].y);
        }
        Point center;
        double R;
        if(n == 1){
            center = Point(store[0].x + 1,store[0].y);
            R = 1;
        }
        else if(1 < n && n <= 4){
            center = Point((store[0].x + store[1].x) / 2,(store[0].y + store[1].y) / 2);
            R = dist(center,store[0]);
        }
        else{
            int cnt = 0;
            while(cnt < (n + 1) / 2){
                cnt = 0;
                int s1 = rand() % n,s2 = rand() % n,s3 = rand() % n;
                while(s1 == s2 || s1 == s3 || s2 == s3){
                    if(s1 == s2) s1 = rand() % n;
                    if(s1 == s3) s3 = rand() % n;
                    if(s2 == s3) s2 = rand() % n;
                }
                center = circumcenter(store[s1],store[s2],store[s3]);
                R = dist(center,store[s1]);
                for(int i = 0;i < n;++i){
                    double r = dist(store[i],center);
                    if(sgn(r,R) == 0) ++cnt;
                }
            }
        }
        printf("%lf %lf %lf
",center.x,center.y,R);
    }
    return 0;
}