BZOJ 2823: AHOI2012信号塔（最小圓覆寫）

2823: [AHOI2012]信号塔

Time Limit: 10 Sec Memory Limit: 128 MB

Description

在野外訓練中，為了確定每位參加集訓的成員安全，實時的掌握和收集周邊環境和隊員資訊非常重要，集訓隊采用的方式是在訓練所在地散布N個小型傳感器來收集并傳遞資訊，這些傳感器隻與設在集訓地中的信号塔進行通信，信号塔接收信号的覆寫範圍是圓形，可以接收到所有分布在該集訓區域内所有N個小型傳感器（包括在該圓形的邊上）發出的信号。信号塔的功率與信号塔接收範圍半徑的大小成正比，因為是野外訓練，隻能使用事先儲備好的蓄電裝置，是以在可以收集所有傳感器資訊的基礎上，還應使得信号塔的功率最小。小龍幫助教官确定了一種信号塔設定的方案，既可以收集到所有N個傳感器的信号，又可以保證這個信号塔的功率是最小的。同學們，你們知道，這個信号塔的信号收集半徑有多大，它應該設定在何處嗎？

Input

共N+1行，第一行為正整數N（1≤N≤1000000），表示隊員個數。接下來N行，每行兩個實數用空格分開，分别是第i個隊員的坐标X

Output

一行，共三個實數（中間用空格隔開），分别是信号塔的坐标，和信号塔 覆寫的半徑。 （注：隊員是否在邊界上的判斷應符合他到圓心的距離與信号塔接收半徑之差的絕對值小于10^-6

Sample Input

5

1.200 1.200

2.400 2.400

3.800 4.500

2.500 3.100

3.900 1.300

Sample Output

2.50 2.85 2.10

HINT

1≤N≤500000

不用說，又是一道求最小圓覆寫的題目，本蒟蒻忍不住吐槽一句：資料太水了！沒加 e p s eps eps的判定直接過了。不會最小圓覆寫的請戳這兒。

代碼如下：

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
struct point{double x,y;}p[N],O;
struct line{double a,b,c;};
double r;
inline double mul(double x){return x*x;}
inline double dis(point x,point y){return sqrt(mul(x.x-y.x)+mul(x.y-y.y));}
inline bool in_check(point x){return dis(O,x)<=r;}
inline point calc(line a,line b){return point{(b.c*a.b-a.c*b.b)/(a.a*b.b-a.b*b.a),(b.c*a.a-a.c*b.a)/(a.b*b.a-b.b*a.a)};}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
	random_shuffle(p+1,p+n+1);
	r=0;
	for(int i=1;i<=n;++i){
		if(in_check(p[i]))continue;
		O.x=p[i].x,O.y=p[i].y,r=0;
		for(int j=1;j<i;++j){
			if(in_check(p[j]))continue;
			O.x=(p[i].x+p[j].x)/2,O.y=(p[i].y+p[j].y)/2;
			r=dis(O,p[i]);
			for(int k=1;k<j;++k){
				if(in_check(p[k]))continue;
				O=calc(line{2*(p[i].x-p[k].x),2*(p[i].y-p[k].y),mul(p[k].x)+mul(p[k].y)-mul(p[i].x)-mul(p[i].y)},line{2*(p[i].x-p[j].x),2*(p[i].y-p[j].y),mul(p[j].x)+mul(p[j].y)-mul(p[i].x)-mul(p[i].y)});
				r=dis(p[i],O);
			}
		}
	}
	printf("%.2lf %.2lf %.2lf",O.x,O.y,r);
	return 0;
}