题意：给你n个点，要求找到一个点，和一个圆心，使得有n/2向上取整个点在圆上，一定有满足条件的点存在
题解：既然一定有解，而且圆上有n/2向上取整个点，那么我们可以通过随机来找三个点来确定一个圆心，和半径，可以看出这三个点在圆上的概率是很大的，注意要特判点数为1，2，3，4的情况
ps：一开始想的是随机两个点，后来发现这样两个点是直径的概率太小了，而且有可能根本不存在直径
#include<bits/stdc++.h>
#include<ext/rope>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std;
using namespace __gnu_cxx; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; inline bool zero(double a)
{
return fabs(a)<eps;
}
struct point{
double x,y;
point(){};
point(double _x,double _y)
{
x=_x;y=_y;
if(zero(x))x=0.0;
if(zero(y))y=0.0;
}
}p[N];
int n;
double R;
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double line(point p1,point p2,point p3)
{
return (p1.y-p2.y)*(p3.x-p2.x)==(p3.y-p2.y)*(p1.x-p2.x);
}
bool ok(point p0)
{
int ans=;
for(int i=;i<n;i++)
{
if(zero(dis(p0,p[i])-R))
{
ans++;
}
}
if(n&)return ans>=(n/+);
else return ans>=(n/);
}
point getmid(point p1,point p2,point p3)
{
point pm={(p1.x+p2.x)/,(p1.y+p2.y)/};
double a1=(p2.x-p1.x),b1=(p2.y-p1.y),c1=-pm.y*(p2.y-p1.y)-pm.x*(p2.x-p1.x);
pm={(p1.x+p3.x)/,(p1.y+p3.y)/};
double a2=(p3.x-p1.x),b2=(p3.y-p1.y),c2=-pm.y*(p3.y-p1.y)-pm.x*(p3.x-p1.x);
pm={(c2*b1-c1*b2)/(a1*b2-a2*b1),(a2*c1-a1*c2)/(a1*b2-a2*b1)};
R=dis(pm,p1);
return pm;
}
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);*/
srand(time(NULL));
int t,cnt=;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
if(n==)
{
point p0={0.0,0.0};
printf("%.10f %.10f %.10f\n",p0.x,p0.y,dis(p0,p[]));
}
else if(n==||n==||n==)
{
point p0={(p[].x+p[].x)/,(p[].y+p[].y)/};
printf("%.10f %.10f %.10f\n",p0.x,p0.y,dis(p0,p[]));
}
else
{
while()
{
int a=rand()%n,b=rand()%n,c=rand()%n;
if(a==b||b==c||a==c)continue;
if(line(p[a],p[b],p[c]))continue;
point p0=getmid(p[a],p[b],p[c]);
if(ok(p0))
{
printf("%.10f %.10f %.10f\n",p0.x,p0.y,R);
break;
}
}
}
}
return ;
}
/******************* ********************/