最小圆覆盖

cwy posted @ 2017年12月31日 18:14 in 板子 , 39 阅读

http://blog.csdn.net/commonc/article/details/52291822

BZOJ2823

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const double eps=1e-6;
struct Point{
	double x,y;
	Point(){}
	Point(double X,double Y){x=X;y=Y;}
	Point operator - (const Point & A) const{
		return Point(x-A.x,y-A.y);
	}
}P[1000010];
int n;
struct Circle{
	Point o;
	double r;
}C;
int sgn(double x){
	if (fabs(x)<eps) return 0;
	else if (x>0) return 1;
	else return -1;
}
double dis(Point A,Point B){
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool IN(Point P,Circle C){
	return (sgn(dis(P,C.o)-C.r)<=0);
}
Circle get1(Point A,Point B){
	Circle t;
	t.o.x=(A.x+B.x)/2,t.o.y=(A.y+B.y)/2;
	t.r=dis(A,B)/2;
	return t;
}
Point rev(Point P){
	return Point(P.y,-P.x);
}
Circle get2(Point A,Point B,Point C){
	Circle O;
	Point P1=Point((A.x+B.x)/2,(A.y+B.y)/2);
	Point Q1=rev(B-A);
	Point P2=Point((A.x+C.x)/2,(A.y+C.y)/2);
	Point Q2=rev(C-A);
	double b=(Q1.x*P1.y-Q1.x*P2.y+P2.x*Q1.y-P1.x*Q1.y)/(Q2.y*Q1.x-Q2.x*Q1.y);
	double a;
	if (sgn(Q1.x)!=0) a=(P2.x+Q2.x*b-P1.x)/Q1.x;
	else a=(P2.y+Q2.y*b-P1.y)/Q1.y;
	O.o.x=P1.x+Q1.x*a;
	O.o.y=P1.y+Q1.y*a;
	O.r=dis(O.o,A);
	return O;
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%lf%lf",&P[i].x,&P[i].y);
	random_shuffle(P+1,P+n+1);
	C.o.x=P[1].x,C.o.y=P[1].y,C.r=0.0;
	FOR(i,2,n)
		if (!IN(P[i],C)){
			C.o=P[i],C.r=0.0;
			FOR(j,1,i-1)
				if (!IN(P[j],C)){
					C=get1(P[i],P[j]);
					FOR(k,1,j-1)
						if (!IN(P[k],C))
							C=get2(P[i],P[j],P[k]);
				}
		}
	printf("%.2f %.2f %.2f\n",C.o.x,C.o.y,C.r);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter