【BZOJ2823】[AHOI2012]信号塔（最小圆覆盖）

题面

BZOJ

洛谷

相同的题：

BZOJ1

BZOJ2

洛谷

题解

模板题。。。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 1000100

const double eps=1e-10;

const double Pi=acos(-1);

struct Point{double x,y,ang;};

bool operator<(Point a,Point b){return (a.ang!=b.ang)?a.ang<b.ang:a.x<b.x;}

Point operator+(Point a,Point b){return (Point){a.x+b.x,a.y+b.y};}

Point operator-(Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}

Point operator*(Point a,double b){return (Point){a.x*b,a.y*b};}

Point operator/(Point a,double b){return (Point){a.x/b,a.y/b};}

double operator*(Point a,Point b){return a.x*b.x+a.y*b.y;}

double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}

double Len(Point a){return sqrt(a.x*a.x+a.y*a.y);}

double Dis(Point a,Point b){return Len(a-b);}

Point Rotate(Point p,double a){double c=cos(a),s=sin(a);return (Point){p.x*c-p.y*s,p.x*s+p.y*c};}

struct Line{Point a,v;};

Point Intersection(Line a,Line b)

{

	Point c=b.a-a.a;

	double t=Cross(b.v,c)/Cross(b.v,a.v);

	return a.a+a.v*t;

}

Line GetHalfLine(Line a)

{

	Point b=a.a+a.v*0.5;

	return (Line){b,Rotate(a.v,Pi/2)};

}

struct Circle{Point o;double r;}O;

void GetCircle(Point *p,int n)

{

	random_shuffle(&p[1],&p[n+1]);

	for(int i=1;i<=n;++i)

		if(Dis(O.o,p[i])>O.r)

		{

			O.o=p[i];O.r=0;

			for(int j=1;j<i;++j)

				if(Dis(O.o,p[j])>O.r)

				{

					O.o=(p[i]+p[j])*0.5;O.r=Dis(p[i],p[j])*0.5;

					for(int k=1;k<j;++k)

						if(Dis(O.o,p[k])>O.r)

						{

							O.o=Intersection(GetHalfLine((Line){p[i],p[j]-p[i]}),GetHalfLine((Line){p[i],p[k]-p[i]}));

							O.r=Dis(O.o,p[i]);

						}

				}

		}

	printf("%.2lf %.2lf %.2lf\n",O.o.x,O.o.y,O.r);

}

int n;Point p[MAX];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);

	GetCircle(p,n);

	return 0;

}