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

hamayanhamayan's blog

Donut Hole [Aizu Competitive Programming Camp 2018 Day 2 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/E

考察過程

1. 食べる中心の座標に向かって直線引くだけでは?
2. WA
3. サンプル2をみるとはみ出している
4. 食べれた部分の中心を計算し直して、直線を引くと通る

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day2/3149662

長方形は対角線の交点を取る直線を引くと、どんな直線でも必ず面積が二等分になる。
中心(0,0)と食べた中心(x,y)を通る線をひけば、元々のドーナツも食べたドーナツも
どちらも二等分されるので、残りの領域も二等分されることになる。
 
しかし、これだとWAする。
食べる予定の部分は元のドーナツをはみ出す場合がある。
そのため、実際に食べた部分のx座標[sx, tx]とy座標[sy, ty]を再計算する。
ここから中心を割り出して同様の計算をすると答え。

int W, H, w, h, x, y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> w >> h >> x >> y;

    int sx = max(-W / 2, x - w / 2);
    int tx = min(W / 2, x + w / 2);
    int sy = max(-H / 2, y - h / 2);
    int ty = min(H / 2, y + h / 2);

    double xx = 1.0 * (sx + tx) / 2;
    double yy = 1.0 * (sy + ty) / 2;

    double ans = 1.0 * yy / xx;
    printf("%.10f\n", ans);
}