ARC029 B問題 : 高橋君と禁断の書

問題. 高橋君と禁断の書

2辺の長さが の矩形 が与えられる．次の 個の質問に答えよ．
　質問：2辺の長さが の矩形 が与えられたときに， が を含むか判定せよ

制約： ，　

解法1. 二分探索

かつ とする． かつ ならば を傾けずに に含むことが可能である．それ以外の場合に， を傾けて に含めることができるかを考える．

まず，下の図のように を底面として角度 だけ傾けるとする．このとき， を含むことができる最小の矩形の横と縦の長さを とすると，
となる． を大きくすると は大きくなり，逆に は小さくなる．また， を小さくすると は小さくなり，逆に は大きくなる．したがって，高さが 以下となる最大の角度 を二分探索で求めた後に， に含まれるかを判定する．このとき， は軸並行に置かれており，高さ ，幅 とする（高さ , 幅 の場合は調べる必要はない）．
同様に， の底面を として，高さが 以下となる最大の角度を求めた後に， （高さ , 幅 ）に含まれるかを判定する．いずれかの場合で成り立つときに は を含むことができる．
　　　　

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = acos(-1);
const ld EPS = 1e-8;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    ld a, b, n;
    cin >> a >> b >> n;
    if (b < a) swap(a, b);

    for (int i = 0; i < n; ++i) {
        ld c, d;
        cin >> c >> d;
        if (d < c) swap(c, d);

        bool can_cont = false;
        can_cont |= (a <= c && b <= d);

        // 底面を b として傾けた時に高さが c 以下となる最大の角度
        ld lb = 0.0, ub = 0.5 * PI;
        for (int j = 0; j < 200; ++j) {
            const ld m = 0.5 * (lb + ub);
            const ld h = a * cos(m) + b * sin(m);

            if (h <= c + EPS) lb = m;
            else ub = m;
        }
        can_cont |= ((a * sin(lb) + b * cos(lb) <= d + EPS)
                     && (a * cos(lb) + b * sin(lb) <= c + EPS));

        // 底面を a として傾けた時に高さが d 以下となる最大の角度
        lb = 0.0, ub = 0.5 * PI;
        for (int j = 0; j < 200; ++j) {
            const ld m = 0.5 * (lb + ub);
            const ld h = b * cos(m) + a * sin(m);

            if (h <= d + EPS) lb = m;
            else lb = m;
        }
        can_cont |= ((b * sin(lb) + a * cos(lb) <= c + EPS)
                     && (b * cos(lb) + b * sin(lb) <= d + EPS));


        if (can_cont) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

解法2. アドホック

antaさんの解法 にリンクがあった．
　Wetzel, John E. "Rectangles in Rectangles." Mathematics Magazine 73, no. 3 (2000): 204-11.

が を含むための必要十分条件は，
　 かつ ,
　　または，
　 かつ
となることである．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = acos(-1);
const ld EPS = 1e-8;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    ld a, b, n;
    cin >> a >> b >> n;
    if (b < a) swap(a, b);

    for (int i = 0; i < n; ++i) {
        ld c, d;
        cin >> c >> d;
        if (d < c) swap(c, d);

        bool can_cont = (a <= c && b <= d);

        double lb = (2 * a * b * d + (b * b - a * a)
                     * sqrt(a * a + b * b - d * d)) / (a * a + b * b);
        can_cont |= ((d + EPS < b) && (lb <= c - EPS));

        if (can_cont) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

アドホックな方法はへぇ〜という感じで証明は読んでいない．幾何が苦手すぎる．
antaさん調べてACしたのか，知っていたのか分からないけど解くの速すぎ．