WARush

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

SRM621 Div1 Easy "RadioRange"

問題

TopCoder Statistics - Problem Statement

この問題は2次元の平面上で起きている。ニコラは座標(0, 0)にあるラジオ局で働いている。(0, 0)を中心とした、半径不明の円の内部にいるときのみ、ラジオを聴くことができる。

ラジオ局の近くには、いくつかの町がある。それぞれの町は正の整数を半径とする円の形をしている。町やラジオ局は部分的あるいは完全に互いに重なっている可能性がある。あなたは全ての町を表すint配列 X, Y, Rが与えられる。i番目の町は座標(X[i], Y[i])を中心とし、半径R[i]である円の形をしている。

もし、部分的にラジオが聞けるような町が存在した場合、そのラジオ局の半径は『悪い』とする。そうでなければ、そのラジオ局の半径は『良い』とする。言い換えると、ある場所ではラジオを聞くことができるが、違う場所ではラジオを聴くことができないような町が存在した場合、半径は『悪い』とする。どの場所でもラジオを聞くことができる町と、全く聞くことができない町のどちらかしか存在しないような半径は『良い』とする。

あなたはint Zが与えられる。ラジオ局の半径は、[0, Z]の区間内で一様にランダムな値となる。半径が『良い』となる確率を返せ。

制約

1 <= 町の数 <= 100
-10^9 <= X[i], Y[i] <= 10^9
1 <= R[i], Z <= 10^9


考えたこと

とりあえず、ラジオ局から見て、町の一番近いポイントと、一番遠いポイントを出す。そのポイント間が悪い半径となるのだが、この区間は町同士で重なる可能性があるため、単純に合計することはできない。

そこで、区間が重なるものはUnion-Find的にどんどん合体させていく。最後まで残った区間の合計が悪い区間となる。


誤差?なにそれおいしいの?

ソースコード

double L[110], R[110];
bool valid[110];

class RadioRange {
public:

    double RadiusProbability(vector <int> X, vector <int> Y, vector <int> Ra, int Z) {
        int N = X.size();
        double z = (double)Z;
        
        // 町単位で悪い区間を出す
        for (int i = 0; i < N; i++) {
            double x = X[i], y = Y[i], r = Ra[i];
            double len = sqrt(x * x + y * y);
            L[i] = max(0.0, len - r);
            R[i] = len + r;
        }

        // 重なっている悪い区間を合体させてく
        memset(valid, true, sizeof(valid));
        while (true) {
            bool update = false;
            for (int i = 0; i < N; i++) {
                if (!valid[i]) continue;
                for (int j = i + 1; j < N; j++) {
                    if (!valid[j]) continue;

                    if (R[i] < L[j] || R[j] < L[i]) continue;

                    L[i] = min(L[i], L[j]);
                    R[i] = max(R[i], R[j]);

                    valid[j] = false;

                    update = true;
                }
            }

            if (!update) break;
        }

        // 悪い区間を合計する
        double sum = 0.0;
        for (int i = 0; i < N; i++) {
            if (valid[i] && L[i] <= z) sum += min(z, R[i]) - L[i];
        }

        return 1.0 - sum / z;
    }
};