【AtCoder Beginner Contest 130】 C Rectangle Cutting の解法
問題文
平面上に長方形があり、4つの頂点の座標は(0, 0), (W, 0), (W, H), (0, H)です。 この長方形の内部または周上の点(x, y)が与えられます。
(x, y)を通る直線で長方形を2つの部分に分割するとき、 面積の大きくない方の面積の最大値を求めてください。
また、その最大値を達成する分割の方法が複数あるかも判定してください。
コード
解答コードは以下になります。(C++で記述)
#include <iostream>
using namespace std;
int main()
{
int W, H, x, y;
cin >> W >> H >> x >> y;
double ans = (double)W * H / 2;
int num = (W == x * 2 && H == y * 2) ? 1 : 0;
cout << ans << " " << num << endl;
return 0;
}
ポイント
【ポイント1】
10行目で求めている ans は、長方形を半分にした面積の値。
→ これが出力すべき1つ目の答えである「面積の最大値」となる
なぜ ans は長方形を半分にした値なのか
長方形の内部または周上の点(x, y)は、(x, y)を通る直線で長方形を2つの部分に分割するとき、必ず長方形を半分にできるため。
【ポイント2】
座標が長方形の中心ならば、最大値を達成する分割の方法が複数ある。
→ これが出力すべき2つ目の答えとなる
11行目で記載の通り、xがWの2倍、yがHの2倍となりうる値であれば(x, y)は中心のため、分割の方法が複数あることを表す「1」を出力。
閲覧ありがとうございます。 コンテンツをいいねと思ってくださった方にサポートいただけると大変嬉しいです!