WARush

SRMの結果とか、解けた問題のコードを書いていきます

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点を三角形の頂点とした時に、
その三角形の角度が全て0度より大きく90度未満である事
  • 三角形の外接円の中に、他の点がない事

上記の条件に当てはまらなくても、4点使えばholeが作れることがある。
その条件は以下の通り

  • 4点を四角形の頂点とした時に、その四角形が長方形になること
(全ての角度が90度である事)
  • 四角形の外接円の中に、他の点がない事

この条件に当てはまる点の中で、外接円の中心までの距離が一番長いものが答え

事後

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;
}