2004/Contest/愛媛大会

Problem G : Color the Map †

問題概要 †

解法 †

グラフに落として DFS との噂．［泉，27 Nov 2004］

辺（線分）を直線の一部とみなして，直線の式と y 座標（x 軸に平行な線分のときは x 座標）の区間を保管しておくと，重複判定が非常に簡単になる．泉のプログラムでは直線の式を ax+by+c=0 として保管した（自由度が 1 つ増えてしまうので適当な制約を与える必要がある）．［泉，28 Nov 2004］

議論・その他 †

• 4色問題かと思いきや，飛び地のせいで5色以上の場合もある．［海津，28 Nov 2004］
• コードに誤りがあったので訂正．［泉，4 Dec 2004］

ファイルを添付する †

izumi_G.cpp

G.cpp