本文共 1242 字，大约阅读时间需要 4 分钟。

题意：给你n个点，让你找出一个点让至少存在n/2个点到这个点的距离为r，输出点的坐标和r。

思路：这个题目中点的个数为1e5，比赛的时候一直都不知道该怎么做，一点思路都没有，感觉不管枚举什么复杂度都很高，赛后才知道这个可以用随机程序完成这个题目，平时也没有怎么做过随机数的题目。我们可以随机枚举三个点，然后通过三个点确定一个圆，确定出圆的圆心，在判断这个圆是否满足要求即可，在求三角形外接圆的时候，可以通过距离方程完成，设圆心的坐标，三个点到圆心的距离相同，解方程即可。 

#include
   
    using namespace std;const int maxn=1e5+50;struct Point{    double x,y;    Point() {}    Point (double a,double b)    {        x=a;        y=b;    }} p[maxn];double dis(int a,int b){    return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));}Point heart(int a,int b,int c){    double a1=p[b].x-p[a].x;    double b1=p[b].y-p[a].y;    double c1=(p[b].x*p[b].x+p[b].y*p[b].y-p[a].x*p[a].x-p[a].y*p[a].y)/2;    double a2=p[c].x-p[b].x;    double b2=p[c].y-p[b].y;    double c2=(p[c].x*p[c].x+p[c].y*p[c].y-p[b].x*p[b].x-p[b].y*p[b].y)/2;    double  x=(b2*c1-b1*c2)/(a1*b2-a2*b1);    double y=(c1*a2-a1*c2)/(b1*a2-a1*b2);    return Point(x,y);}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        for(int i=0; i
    
     =n)                {                    printf("%lf %lf %lf\n",h.x,h.y,dis(n,a));                    break;                }            }        }    }//    cout << "Hello world!" << endl;    return 0;}
    
   

转载地址：http://wdgsi.baihongyu.com/