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，泉］

ファイルを添付する †

jewels.out.txt

izumi_F.cpp

jewels.txt