20求调!!!!!
查看原帖
20求调!!!!!
819682
Exile_Code楼主2024/1/28 23:01
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <functional>
#include <unordered_map>
#include <unordered_set>


#define ull             unsigned long long 
#define ll              long long
#define pii             pair<ll ,ll>
#define ft              first
#define sd              second
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,n)       for(ll (i)=0;(i)<(n);(i)++)   
#define forne(i,n)      for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n)      for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n)     for(ll (i)=n;i>=1;i--)
#define vv              vector
#define inf32           INT32_MAX
#define inf64           INT64_MAX
#define LD              double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
#define eps				1e-10
const int N = 4e5 + 100;
const int mod = 998244353;
ll T;


LD a;


//点类
struct Point {
	LD x, y;
	Point(LD x, LD y) { this->x = x;	this->y = y; }
	Point() {}
#define line Point 
	//点的加减乘运算
	Point operator+(Point b) { return Point(this->x + b.x, this->y + b.y); }
	Point operator-(Point b) { return Point(this->x - b.x, this->y - b.y); }
	Point operator*(LD t) { return Point(this->x * t, this->y * t); }
	LD operator*(Point b) { return this->x * b.x + this->y * b.y; }
	bool operator==(Point b) { return this->x == b.x && this->y == b.y; }
	Point operator/(LD t) { return { this->x / t, this->y / t }; }
};
struct Line {
	Point s, e;
	ll id;
	bool operator==(Line b) {
		return this->e == b.e && this->s == b.s;
	}
};
struct Circle { Point p; LD r; };
class Geomtry_tool {
public:
	//求长度
	static LD len(line a) { return sqrt(a.x * a.x + a.y * a.y); }
	//求两点距离
	LD dis(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
	//两个向量求角度,使用的是余弦定理求arccos
	static LD angle(line a, line b) { return acos(a * b / len(a) / len(b)); }
	//两个向量求叉积
	static LD cross(line a, line b) { return a.x * b.y - a.y * b.x; }
	//epslion,判断是否等于0
	static int sgn(LD x) { return fabs(x) <= eps ? 0 : x > 0 ? 1 : -1; }
	//防止负0的发生
	static void zero(Point& a) { if (fabs(a.x) <= eps)a.x = 0; if (fabs(a.y) <= eps)a.y = 0; }
	//可以用来判断c在b的左侧还是右侧
	//大于0,c在ab左侧;小于0,c在ab右侧;等于0,三点共线
	static LD cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
	//三点点积ab*ac
	static LD dot(Point a, Point b, Point c) { return (b - a) * (c - a); }
	//判断直线与线段的交点情况,在同侧则无交点;
	//如果是判断线段与线段有无交点,则需要分别设ab,cd为直线,进行两次判断
	static bool l_S_inter(Point a, Point b, Point c, Point d) {
		return sgn(cross(a, b, c) * cross(a, b, d)) <= 0;//直线与线段
	}
	//线段与线段
	static bool S_S_inter(Point a, Point b, Point c, Point d) {
		return l_S_inter(a, b, c, d) && l_S_inter(c, d, a, b);
	}
	//求两直线的交点
	static Point getNode(Point a, line u, Point b, line v) {
		LD t = cross((a - b), v) / cross(v, u);//求面积之比
		return a + u * t;
	}
	//逆时针旋转b
	static Point rotate(Point a, LD b) { //将某点绕原点逆时针旋转b角度
		return { a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b) };
	}

	//求多边形面积
	static LD get_S(vv<Point>& p) {
		int k = p.size() - 1; LD res = 0;
		for (int i = 2; i < k; i++)
			res += cross((p[i] - p[1]), (p[i + 1] - p[1]));
		return res / 2;
	}

	//求中垂线
	static Line midperp(Point a, Point b) {
		return { (a + b) / 2,rotate(b - a, PI / 2) };
	}

};

//最小圆覆盖
class Minimum_circle {
public:
	Geomtry_tool fn; Circle C;
	//求两点共圆
	Circle cover(Point a, Point b) {
		return { (a + b) / 2,fn.dis(a,b) / 2 };
	}
	Point cross(Line a, Line b) {//求ab两线交点
		return fn.getNode(a.e, a.s-a.e, b.e, b.s-b.e);
	}
	//求三点共圆
	Circle cover(Point a, Point b, Point c) {
		Line u = fn.midperp(a, b), v = fn.midperp(a, c);
		Point p = cross(u, v);
		return { p,fn.dis(p,a) };
	}
	//增量法
	void increment(vv<Point>& p) {
		C = { p[1], 0 };
		int n = p.size() - 1;
		for (int i = 2; i <= n; i++) {
			if (C.r < fn.dis(C.p, p[i])) {
				C = { p[i], 0 }; //一点圆
				for (int j = 1; j < i; j++) {
					if (C.r < fn.dis(C.p, p[j])) {
						C = cover(p[i], p[j]); //两点圆
						for (int k = 1; k < j; k++)
							if (C.r < fn.dis(C.p, p[k]))
								C = cover(p[i], p[j], p[k]); //三点圆
					}
				}
			}
		}
	}
};

void solve() {

	int n; cin >> n;
	vv<Point>nums(n + 1);
	forne(i, n)
		cin >> nums[i].x >> nums[i].y;
	random_shuffle(nums.begin() + 1 ,nums.end()); //随机化

	Minimum_circle mc;
	mc.increment(nums);

	printf("%.10lf\n%.10lf %.10lf\n", mc.C.r, mc.C.p.x, mc.C.p.y);
}
int main() {

	//std::ios::sync_with_stdio(false);
	T = 1;
	//cin >> T;

	while (T--)
		solve();

}
2024/1/28 23:01
加载中...