Health Check
問題作成:荒木
解答作成:荒木、牟田
英訳:菅原
解説:荒木
問題
• 凸多角形Pの外側に多
角形Q(凸とは限らない)
がある。ある点Rを中心
にQを、Pにぶつからな
いように、時計回りに何
度回転させることが出
来るか求めよ。
解法①
• 次の二つの場合を考えなければならない
– 内側の多角形の頂点が外側の多角形の辺に衝
突する時
– 外側の多角形の頂点が内側の多角形の辺に衝
突する時
解法②
• 内側の多角形の頂点を反時計回りに回した
時に、外側の多角形の辺に衝突する角度を
列挙
• 外側の多角形の頂点を時計回りに回したとき
に、内側の多角形の辺に衝突する角度を列
挙
• これらの角度のうち最小のものを求めればよ
い
解法③
• 衝突する点を求めるためには、線分と円の交
点を求めればよい。
• 直線と円の交点を求めて、それが線分の範
囲に入っているかどうか調べる。
結果
• Submit: 12
• Accept: 5 (First Accept: Unknown 134分)