はまやんはまやんはまやん

hamayanhamayan's blog

ヒバラ海に沈む遺跡 [パソコン甲子園2015 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0323

考察過程

1. 全ての円が重なる部分での最大距離が求まればいい
2. 流石にその部分を作るのはヤバすぎて無理そう
3. だが、全ての円が重なる部分の海岸線の領域は簡単に求められる
4. 海岸線の座標がわかったときに、最大距離を求めることはできないか
5. これはできそう。全ての円について、その地点での最大距離を求めて、その最小値である
6. ここまで来ると三分探索が頭をよぎる
7. 上に凸になるかを考えると、なりそうな予感がある
8. 反例を探しても特に見当たらないので、三分探索して最大距離の最大を求めたら答え

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0323/judge/3142219/C++14

まず、全ての円が重なる部分の海岸線の領域を求めよう。
円の海岸線の領域は[X-R,X+R]なので、全ての円について領域の重なりをとればいい。
あとは、その区間の中で最大距離が最大となるxを調べる。
三分探索しよう。
 
問題は、海岸線の座標がxであるときの最大距離の求め方。
ある円について、海岸線の座標がxであるときの距離yは中心との距離d=abs(X - x)を使って、三平方より
d^2 + y^2 = R^2なので、y=sqrt(R^2 - d^2)で計算できる。
全ての円についてこの距離を計算して、最小値が最大距離となる。

int N, X[101010], R[101010];
//---------------------------------------------------------------------------------------------------
double f(double x) {
    double res = inf;
    rep(i, 0, N) {
        // d^2 + y^2 = R^2
        double d = abs(x - X[i]);
        double yy = 1.0 * R[i] * R[i] - d * d;
        double y = sqrt(yy);
        chmin(res, y);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> R[i];

    double a = -inf, b = inf;
    rep(i, 0, N) {
        chmax(a, (double)(X[i] - R[i]));
        chmin(b, (double)(X[i] + R[i]));
    }

    double t = findMaxReal(a, b, f);
    double ans = f(t);
    printf("%.10f\n", ans);
}