読者です 読者をやめる 読者になる 読者になる

三角形と円の位置関係判定

AOJ0153 を解いたメモ。

三角形の頂点の座標と円の中心座標及び半径が与えられた時に、

  • 円が三角形に含まれる場合 a
  • 三角形が円に含まれる場合 b
  • それ以外の場合で、共通部分がある場合には c
  • 共通部分がない場合には d

を出力します。
但し線や点同士が接している場合も「共通している」判定です。

以下、上手くいった方法。

  • 三角形の各頂点が全て円の中に含まれている場合 : b
  • 三角形の各頂点の内円の中に含まれているものと含まれていないものがある場合 : c
  • 三角形の各頂点が全て円の中に含まれていない場合
    • 三角形の辺と円の中心の距離 < 円の半径 な辺が存在する場合 : c
    • 三角形の全ての辺について、円の中心との距離≧円の半径 な場合
      • 三角形の中に円の中心が存在する場合(CCWで判定) : a
      • 三角形の外に円の中心が存在する場合
        • 円周と接する辺が存在する場合 : c
        • 円周と接する辺が存在しない場合 : d

最後の円周と接する条件を見落としていて、WAをたくさん貰ってしまった…。
結構エレファントになってしまったので、もっとこうするとスマートに判定できるヨ!的な情報あったらぜひ教えてください。