kmjp's blog

競技プログラミング参加記です

AtCoder ABC #151 : F - Enclose All

GCJを思い出す。
https://atcoder.jp/contests/abc151/tasks/abc151_f

問題

2次元座標上にN個の点の座標が与えられる。
全点を内包する円の最小半径を求めよ。

解法

この円は以下のいずれかを満たすはずである。

  • ある2点を直径とする
  • 円の中心はある面積が正の三角形の3点の外心である

よって2点・3点を総当たりして円の中心の座標の候補を求め、そこから全点を含められる半径を求めよう。
三角形の外心の座標はWikipediaが参考になる。
外接円 - Wikipedia

int N;
ll X[51],Y[51];

double ret;

void hoge(double x,double y) {
	double r=0;
	int i;
	FOR(i,N) r=max(r,hypot(X[i]-x,Y[i]-y));
	ret=min(ret,r);
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	ret=1e9;
	
	FOR(z,N) FOR(y,z) {
		double rx=(X[y]+X[z])/2.0;
		double ry=(Y[y]+Y[z])/2.0;
		hoge(rx,ry);
		
		FOR(x,y) {
			double a=hypot(X[y]-X[z],Y[y]-Y[z]);
			double b=hypot(X[z]-X[x],Y[z]-Y[x]);
			double c=hypot(X[x]-X[y],Y[x]-Y[y]);
			
			if(abs(a+b-c)<1e-9) continue;
			if(abs(a+c-b)<1e-9) continue;
			if(abs(c+b-a)<1e-9) continue;
			
			double rx=(a*a*(b*b+c*c-a*a)*X[x]+b*b*(a*a+c*c-b*b)*X[y]+c*c*(b*b+a*a-c*c)*X[z])/(a*a*(b*b+c*c-a*a)+b*b*(a*a+c*c-b*b)+c*c*(b*b+a*a-c*c));
			double ry=(a*a*(b*b+c*c-a*a)*Y[x]+b*b*(a*a+c*c-b*b)*Y[y]+c*c*(b*b+a*a-c*c)*Y[z])/(a*a*(b*b+c*c-a*a)+b*b*(a*a+c*c-b*b)+c*c*(b*b+a*a-c*c));
			hoge(rx,ry);
		}
	}
	_P("%.12lf\n",ret);
	
}

まとめ

GCJ2010の経験が活きた。