Codeforces #168 E "The Last Hole!"
問題
http://codeforces.com/contest/275/problem/E
訳
平面上にN個の円がある。
i番目の円の中心は(xi, yi)として整数で与えられる。
時間0から円が同時に大きくなり始める。言い換えると、
時間tの時、全ての円の半径は同じくtとなっている。
円の部分は黒く塗りつぶされ、それ以外は白くなっている。
なので、各瞬間で、平面はいくつかの白と黒の部分で構成される事となる。
円は他の円と重なっても大きくなり続けるところに注意。
白い部分で閉ざされている部分をholeであるとする。
例えば、この図では、
赤く縁取られている2つの部分がholeとなる。
円が大きくなり続けるとholeが作られるが、
それがいつか必ず消える事が簡単に想像できる。
与えられた円の情報から、最後に残ったholeがいつ消えるのかを返せ。
また、holeが作られる事がなければ、-1を返せ。
制約
1 <= N <= 100
-10000 <= 円の中心座標(x y) <= 10000
考えた事
任意の円の中心3点で、holeが作られる条件は以下の通り
- 3点を三角形の頂点とした時に、
- 三角形の外接円の中に、他の点がない事
上記の条件に当てはまらなくても、4点使えばholeが作れることがある。
その条件は以下の通り
- 4点を四角形の頂点とした時に、その四角形が長方形になること
- 四角形の外接円の中に、他の点がない事
この条件に当てはまる点の中で、外接円の中心までの距離が一番長いものが答え
事後
5、6時間かかった
もー疲れた
ソースコード
/* プロトタイプ関数 */ void getVec( int ax, int ay, int bx, int by, int* vx, int* vy ); double getLen( double ax, double ay, double bx, double by ); double cosFromVec( int v1x, int v1y, int v2x, int v2y ); void getCenter( double ax, double ay, double bx, double by, double cx, double cy, double* rx, double* ry ); double getTimeOfEraseHole( int ai, int bi, int ci ); const double PI = 3.14159265258979; const double EPS = 1e-5; int N; int xs[100]; int ys[100]; double coss[100][100][100]; //cos[i][j][k] ベクトルij ikのcosの値 int main() { // 入力 cin >> N; for( int i = 0; i < N; i++ ){ cin >> xs[i] >> ys[i]; } // 全ての3点の組み合わせでcosの値を求める for( int a = 0; a < N; a++ ) for( int b = 0; b < N; b++ ) for( int c = 0; c < N; c++ ){ if( a == b || b == c || c == a ) continue; int abx, aby, acx, acy; getVec( xs[a], ys[a], xs[b], ys[b], &abx, &aby ); getVec( xs[a], ys[a], xs[c], ys[c], &acx, &acy ); coss[a][b][c] = cosFromVec( abx, aby, acx, acy ); } double res = 0; // 全てが90未満の三角形がないか調べる for( int a = 0; a < N; a++ ) for( int b = a + 1; b < N; b++ ) for( int c = b + 1; c < N; c++ ){ if( coss[a][b][c] > EPS && coss[b][c][a] > EPS && coss[c][a][b] > EPS ){ res = max( res, getTimeOfEraseHole( a, b, c ) ); } } // 長方形がないか調べる for( int a = 0; a < N; a++ ) for( int b = 0; b < N; b++ ) for( int c = 0; c < N; c++ ){ if( a == b || b == c || c == a ) continue; if( abs(coss[a][b][c]) > EPS ) continue; for( int d = 0; d < N; d++ ){ if( a == d || b == d || c == d ) continue; if( abs(coss[d][b][c]) <= EPS ){ double l1 = getLen( xs[a], ys[a], xs[d], ys[d] ); double l2 = getLen( xs[b], ys[b], xs[c], ys[c] ); if( abs(l1 - l2) <= EPS ){ res = max( res, getTimeOfEraseHole( a, b, c ) ); } } } } // 出力 if( res == 0 ){ cout << -1 << endl; }else{ printf( "%.4lf\n", res ); } } /* 2点のベクトルを返す */ void getVec( int ax, int ay, int bx, int by, int* vx, int* vy ){ *vx = ax - bx; *vy = ay - by; } /* 2点間の距離を返す */ double getLen( double ax, double ay, double bx, double by ){ double lx = abs( ax - bx ); double ly = abs( ay - by ); return sqrt(lx * lx + ly * ly); } /* 2ベクトルのコサインを返す */ double cosFromVec( int v1x, int v1y, int v2x, int v2y ){ double n = v1x * v2x + v1y * v2y; double len = getLen( v1x, v1y, 0, 0 ) * getLen( v2x, v2y, 0, 0 ); return n / len; } /* 3点の外接円の座標を求める */ void getCenter( double ax, double ay, double bx, double by, double cx, double cy, double* rx, double* ry ){ // ax + by + c = 0; // dx + ey + f = 0; double a = bx - ax; double b = by - ay; double c = ax*(ax-bx) + ay*(ay-by) - ((ax-bx)*(ax-bx)+(ay-by)*(ay-by))/2; double d = cx - ax; double e = cy - ay; double f = ax*(ax-cx) + ay*(ay-cy) - ((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy))/2; *rx = (b*f-c*e) / (a*e-b*d); *ry = (a*f-c*d) / (b*d-a*e); } /* 3点から作られるホールが消える時の時間を返す */ double getTimeOfEraseHole( int a, int b, int c ){ double rx, ry; // 外接円の中心 getCenter( xs[a], ys[a], xs[b], ys[b], xs[c], ys[c], &rx, &ry ); double len = getLen( xs[a], ys[a], rx, ry ); // 中心により近い点はないか? bool ok = true; for( int i = 0; i < N; i++ ){ double l = getLen( xs[i], ys[i], rx, ry ); if( len > l && abs(l - len) > EPS ){ ok = false; } } return ok ? len : 0; }