Problem G
Illuminating the Hedge
オリジナル（三廻部出題）
中嶋・松崎
あらすじ

某所に荒れ果てた宿泊施設があった…

どう見ても八王子です。本当に（ry

宿泊客に不人気… （´･ω･｀）

名案ｷﾀ━━━━(ﾟ∀ﾟ)━━━━ｯ!!

生垣にイルミネーション施せば万事解決!!!

（；＾ω＾） ちょwww おまwww
概要


生垣の両端をケーブルで接続
最短は？
結果

Submissions: 47

Accepted:


_oop (105)
Nimrod (297)
まず第一に

凸包ではない

グラフ作成 + Dijkstra
想定解答

摂動
摂動：注意点（1/2）

解の精度に注意


通過可能判定：ずらした点群で
距離の測定：元の点群で

「ずらす幅 ≪ 許容誤差」なら省略可？
摂動：注意点（2/2）

ずらす幅に注意


整数座標なら，点と線分の距離は最接近時でも
 /hypot( xmax  xmin , ymax  ymin ) 以上
今回は 1/ 200 2  0.0035... 以下なら OK

0.003 で確認済
通れない…
実装

中嶋：125 行





20：ライブラリ（Dijkstra）
40：ライブラリ（線分関係）
20：#include, I/O
45：摂動，グラフ作成
信頼できるライブラリを！

偏光板の実験

Document 7439585