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の経験が活きた。