ARC029-B:高橋君と禁断の書

問題

https://beta.atcoder.jp/contests/arc029/tasks/arc029_2

縦 A センチ、横 B センチのノートが与えられる。また N 個の箱が与えられ、箱 i は縦 C_i, 横 D_i センチである。ノートを回転させて箱に入るかどうか求めよ。

考え方

座標の回転が必要かと思いきやそうではなく、パズルっぽい問題。縦 A, 横 B のノートを θ 度回転させたときに縦,横が何センチになるか調べると、以下にようになることがわかる。

f:id:d_tutuz:20181102000114p:plain

縦が b*cosθ + a*sinθ、横が b*sinθ + a*cosθ となる。

後は回転する角度θについて二分探索することで条件を満たすθを求めることができるので、そのようなθが存在すれば YES そうでなければ NO となる。

Submission #3501616 - AtCoder Regular Contest 029

ポイント

類題