1999/Contest/京都大会

Problem F : Heavenly Jewels

問題概要

領域 U = [0,10000]×[0,10000] 上の 3 点 A,B,C が与えられる.点 A からの距離が他の 2 点からの距離よりも小さくなるような点の集合からなる領域 S の領域 U に対する割合を求める.

解法

次の 6 本の直線の交点をすべて求める(最大 13 個).

  • 直線 x = 0
  • 直線 x = 10000
  • 直線 y = 0
  • 直線 y = 10000
  • 2 点 A,B の垂直二等分線
  • 2 点 A,C の垂直二等分線

得られた点のうち,次の 2 つの条件をいずれも満たす点すべてを頂点とする多角形(常に凸多角形になる)が求める領域 S である.[17 Dec 2004,泉]

  • 領域 U に含まれる.
  • 点 A からの距離が他の 2 点からの距離よりも小さい.

議論・その他

ソースコードの間違いを修正した.ついでに ZOJ にて正当性を確認.[01 Mar 2006,泉]


ファイルを添付する

filejewels.out.txt 815件 [詳細] fileizumi_F.cpp 839件 [詳細] filejewels.txt 767件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filejewels.out.txt 815件 [詳細] fileizumi_F.cpp 839件 [詳細] filejewels.txt 767件 [詳細]

Last-modified: 2009-11-06 (金) 13:27:11 (3328d)