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