1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-6;
int n;
double R;
struct node
{
double x;
double y;
}p[N],ans;
node solve(node a, node b, node 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;
if(d<eps) return {1e18,1e18};
return {a.x + (c1*b2 - c2*b1)/d, a.y + (a1*c2 -a2*c1)/d};
}
void printf(double x,double y,double r)
{
printf("%.6f %.6f %.6f\n",x,y,r);
}
bool same(double x,double y)
{
return fabs(x-y)<eps;
}
double dis(node a, node b)
{
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
void work()
{
int need = (n+1)/ 2;
while (true)
{
int i =rand() % n;
int j =rand() % n;
int k =rand() % n;
node point = solve(p[i], p[j], p[k]);
if(abs(point.x)>1e9||abs(point.y)>1e9) continue;
double r = dis(point, p[i]);
int num = 0;
for ( i = 0; i < n; i++)
{
if (same(dis(p[i],point),r))num++;
if (num == need) {
printf("%.6f %.6f %.6f\n", point.x, point.y, r);
return;
}
}
}
}
void sol()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
double x,y;
scanf("%lf %lf", &x, &y);
p[i]={x,y};
}
double one = 1;
if(n==1)
printf("%.6f %.6f %.6f\n",p[0].x+1,p[0].y,one);
else if(n>=5)
work();
else
printf("%.6f %.6f %.6f\n",(p[0].x+p[1].x)/2,(p[0].y+p[1].y)/2,dis(p[0],p[1])/2);
}
int main()
{
srand(time(0));
int t;
scanf("%d", &t);
while (t--)sol();
}
|