3150 魔法圆

哈利波特在城市里布置了n个法阵（2 <= n <= 50000），现在给出这n个法阵的坐标，请你帮助哈利波特选取一个圆，使得至少个法阵在圆周上（到圆心的距离为圆的半径，可以有不超过0.01的误差），以便哈利波特施展魔法对抗魔兽。

输入

第一行一个整数n，表示法阵个数
接下来n行每行两个整数x y表示法阵的坐标

输出

一行三个整数x y R，分别表示该圆的圆心横坐标、纵坐标和半径

数据范围

10% 2 <= n <= 10
30% 2 <= n <= 300
60% 2 <= n <= 3000
100% 2 <= n <= 50000

输入样例

7
1 1
1 0
1 -1
0 1
-1 1
0 -1
-1 0

输出样例

0 0 1

解析：

N的范围是1e5，所以枚举点是行不通的，因为3个点可以确定一个圆，所以我们只要每次随机三个点然后来确定一个圆，最后在判断这个圆是否可行。因为至少有一半的点是在圆上所以随机的次数是非常少的。对于小于5个点的要直接特判。

放代码：

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <cmath>
using namespace std;
const double eps=1e-3;
struct P
{
    double x,y;
} sb[100005];
P Yuanxin(P a,P b,P c)     //(已知三点求圆心坐标)
{
    P q;
    q.x=((c.y-a.y)*(c.y-b.y)*(b.y-a.y)+(a.x*a.x-b.x*b.x)*(c.y-a.y)-(a.x*a.x-c.x*c.x)*(b.y-a.y))/(2*((c.y-a.y)*(a.x-b.x)-(a.x-c.x)*(b.y-a.y)));
    q.y=((c.x-a.x)*(c.x-b.x)*(b.x-a.x)+(a.y*a.y-b.y*b.y)*(c.x-a.x)-(a.y*a.y-c.y*c.y)*(b.x-a.x))/(2*((c.x-a.x)*(a.y-b.y)-(a.y-c.y)*(b.x-a.x)));
    return q;
}
int main()
{
    int t;
    srand((unsigned int)time(NULL));
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++)scanf("%lf%lf",&sb[i].x,&sb[i].y);
    if(n == 1 || n == 2)
    {
        printf("%lf %lf %lf\n",sb[0].x + 1,sb[0].y,1.0);
    }
    if(n == 3 || n == 4)
    {
        printf("%lf %lf %lf\n",(sb[0].x+sb[1].x)/2,(sb[0].y+sb[1].y)/2,sqrt(((sb[0].x-sb[1].x)*(sb[0].x-sb[1].x))+((sb[0].y-sb[1].y)*(sb[0].y-sb[1].y)))/2);
    }
    while(1)
    {
        int a = rand()%n;
        int b = rand()%n;
        int c = rand()%n;
        if(a == b || a == c || b == c)continue;
        double x1,x2,x3,y1,y2,y3;
        x1=sb[a].x;x2=sb[b].x;x3=sb[c].x;
        y1=sb[a].y;y2=sb[b].y;y3=sb[c].y;
        if((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3))continue;
        P yuanxin = Yuanxin(sb[a],sb[b],sb[c]);
        double r = sqrt(((sb[a].x-yuanxin.x)*(sb[a].x-yuanxin.x))+((sb[a].y-yuanxin.y)*(sb[a].y-yuanxin.y)));
        int sum=0;
        for(int i = 0 ; i < n ; i++)
        {
            if(fabs(sqrt(((sb[i].x - yuanxin.x) * (sb[i].x - yuanxin.x)) + ((sb[i].y - yuanxin.y) * (sb[i].y - yuanxin.y))) - r) <= eps)
                sum++;
        }
        if(2 * sum >= n)
        {
            printf("%lf %lf %lf\n",yuanxin.x,yuanxin.y,r);
            break;
        }
    }
    return 0;
}