Page 1 of 212

NEERC Southern Subregional 2006

SGU 315 ~ 325

Problem A. The Highway Belt
給定一組平麵線段,求從中能得到周長最長的 "星狀線"。
(既包圍原點,且與從原點出發的每一條射線有且僅有一個交點。。。
Tags: 計算幾何, DP
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=701534
先計算幾何求出所有交點,和所有交點的鄰接表。。(方法類似 Areas。。
。。再枚舉起始點。。(既所有線段同 x 軸正方向的交點,
。沿著 [0, 2pi) 的幅角做常規動態規劃即可。。

ゆっくり読んでください ...

Page 1 of 212