AtCoder Regular Contest 029 B 高橋君と禁断の書

問題

arc029.contest.atcoder.jp

解き方

二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。

計算量

二分探索の繰り返し回数をkとすると O(kn)

code