每日一水第47弹2014 NWERC

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77953#problem/A

给你两个多边形,一个在另一个的里面,可以想象成我们学校操场里面的塑胶跑道,分外圈,内圈,现在有一个人绕着内圈跑步,求最短的内圈周长。

假如没有外面那个多边形的存在,显然,最短路就是里面那个多边形的凸包的周长。

由于外圈的存在。有些凸包的边会被挡住,所以可以有这样一个想法,先求凸包,对于凸包上相邻的两个点求最短的走法。

将凸包相邻两个点之间的内圈点都加入点集,再把所有外圈在这个局部多边形(凸包上相邻的两个点以及中间那些凹陷进去的点构成的多边形)里面的点也加入点集。对这个点集暴力连边,求最短路即可。

此题一不小心就陷入各种坑里面。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注