けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 130 C - Rectangle Cutting (茶色, 300 点)

長方形を直線で真っ二つに割る方法について

  • 直線が長方形の対角線の交点を通る
  • 直線が長方形を二等分する

というのは同値だという話。結構、中学受験の算数では定番の話だったりする。

問題へのリンク

問題概要

二次元平面上で  (0, 0), (W, 0), (0, H), (W, H) を頂点とした長方形と、その内部または周上の点  (x, y) があたえられる。

 (x, y) を通る直線で長方形を真っ二つに分割する方法のうち、切り取られた二つの断片のうちの面積の小さい方の面積の最大値を求めよ。

また、その最大を達成するような直線が複数通りありうるかどうかを判定せよ。

制約

  •  1 \le W, H \le 10^{9}

考えたこと

答えは、長方形の面積の半分!!!!!!!!

具体的には、

  •  (x, y)
  •  (\frac{W}{2}, \frac{H}{2})

を通る直線を考えればよい。ここで  x = \frac{W}{2}, y = \frac{H}{2} だったら直線が複数通りありえて、そうでなければ一意である。

なお、 x == \frac{W}{2} といった関係式の判定は誤差をなくすために  2x == W と判定した方が無難。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    long long W, H, x, y;
    cin >> W >> H >> x >> y;
    double res = (double)(W) * H / 2;
    cout << fixed << setprecision(10) << res << " ";

    if (x*2 == W && y * 2 == H) cout << 1 << endl;
    else cout << 0 << endl;
}