zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC130-C「Rectangle Cutting」です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
// intで丸め誤差が出ないようにdoubleで受け取ることにする
double W=0, H=0, x=0, y=0, ans=0;
int main(){
cin >> W >> H >> x >> y;
// WやHがintだとここで誤差が発生する
ans = W * H / 2;
// 小数点以下10桁まで表示するようにする
cout << fixed << setprecision(10);
// とりあえず面積の半分を表示
cout << ans << " ";
// (x, y)が中心かどうか判断
if (W/2==x and H/2==y) cout << 1 << endl;
else cout << 0 << endl;
}ポイント
今回おさえるべき内容
数学的な考察を必要とする問題に慣れる
数学的な考察が必要になる問題でした。長方形を2分割するときに「大きくない方を最大化する」というのは，言い換えれば「分割された2つの面積の差を最小化する」ということに他なりません。すると，任意の長方形は中心を通る直線で2分割できますので，出力の1つ目はどのケースにおいても「長方形の面積の半分」であることに気付きます。
一方で，最初に中心以外の点が与えられた場合には，その点と中心を通る直線は一意に定まります。最初に中心が与えられた場合には，任意の直線によって長方形は2分割されます。以上より，最初に長方形の面積の半分を出力して，次に与えられた点が中心かそうでないかを判断してから，0か1を出力すればOKです。
コメント