精度挂了咋办捏
查看原帖
精度挂了咋办捏
778011
DreamLand_zcb楼主2023/6/9 17:25
#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a))
#define double long double
using namespace std;

const double eps = 1e-9;
int n; 
struct node {
	double x, y;
}t[100005];
double r;//半径答案 
node p;//坐标答案 
double dist(node a, node b)
{
	double u = (a.x - b.x), v = (a.y - b.y);
	return sqrt(u * u + v * v);
}
void work(node u, node v, node w)
{
	double a = 2 * (u.x - v.x);
	double b = 2 * (u.y - v.y);	
	double c = u.x * u.x + u.y * u.y - v.x * v.x - v.y * v.y;
	double d = 2 * (v.x - w.x);
	double e = 2 * (v.y - w.y);
	double f = v.x * v.x + v.y * v.y - w.x * w.x - w.y * w.y;
	double g = a * e - b * d;
	double px = (c * e - f * b) / g;
	double py = (a * f - d * c) / g;
	p = (node){px, py};
	r = dist(p, u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++)	cin >> t[i].x >> t[i].y;
	random_shuffle(t+1, t+n+1);
	r = 0;p = t[1];
	for(int i=2;i<=n;i++)
	{
		if(dist(p, t[i]) < r - eps)	continue;
		for(int j=1;j<i;j++)
		{
			if(dist(p, t[j]) < r - eps)	continue;
			p.x = (t[i].x + t[j].x) / 2;
			p.y = (t[i].y + t[j].y) / 2;
			r = dist(t[i], t[j]) / 2;
			for(int k=1;k<j;k++)
			{
				if(dist(p, t[k]) < r - eps)	continue;
				work(t[i], t[j], t[k]);
			}
		}
	}
	cout << fixed << setp(10) << r << endl;
	cout << fixed << setp(10) << p.x << " " << p.y;
//  printf("%.10lf\n%.10lf %.10lf", r, p.x, p.y);
	return 0;
}

2023/6/9 17:25
加载中...