pku3151 运动规划
1个评论14次阅读2008.09.14 0:15; 作者：Felicia
这个题非常麻烦。
我的做法是：
amath
- 把矩形按半径`r`扩展为新的矩形和圆
- 求出所有圆的公切线和切点，以及`s,t`两点与所有圆的切线和切点
- 判断切点是否合法，即判断切点是否被矩形或圆覆盖
- 删去所有不合法的切线，得到合法的切线
- 将圆弧上的点排序，枚举每个`1/4`圆弧上的相邻两点，若他们都是合法点，并且这个圆弧不与任何矩形和圆相交，那么定义他们之间的距离为他们的弧长
- 将以上处理得到的两点间距离加入无向图中，求`s`到`t`的最短路。
endamath
做这个题的时候发生了非常诡异的现象，在 TJU 上用 g++ 交AC，PKU 上则 RE，但是用 C++ 交却 AC了……有谁知道是为什么呢？
发表回复
Felicia | 1F
九月 14th, 2008 at 00:18
貌似跟编译参数有关……还是弄不懂。我自己测试的时候同样的程序加 -O 和不加，跑出来的结果是不一样的……