~~

看了iAKiak大哥的算法 的确很不错 不过 实现起来也不是很顺利(呵呵 或许是我的水平太低了吧)

这次的比赛,真的太便宜我了,不过 我会为下次的比赛做好准备的,同时,也希望大家拿出自己最好的代码

ok??

[quote]即使用了凸包算法,但是在最坏的情况下,可以专门出数据,还是O(n^2).[/quote]

同意这个观点，而且如果真遇到这样的输入数据加入凸包算法的代码比最慢 O(n^2) 的还得慢（多加个步骤）。但据说 tongji 的测试数据比较弱，只需要用凸包+枚举就能搞定。某高人 @maigo 提了个“对踵点”法，用于得出凸包后得最大距离，描述如下：

[quote]
下面介绍一种“对踵点法”，求凸包以后的步骤的时间复杂度仅为O(n)。
　　先给出“对踵点”的定义：如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。下面将证明最远距离点对一定是一对对踵点。
 　　观察图1，设∠1+∠2≤180°，∠3+∠4≤180°。那么如果∠1≥∠4，则由于∠1+∠2≤180°，一定可过B、E作两条平行线使边AB落在其中一条上；反之，则可过B、E作两条平行线使DE落在其中一条上。也就是说，当一条线段截凸包所成的两组“同旁内角”之和均不超过180°时，这条线段的两个端点是一对对踵点。因此，若一条线段的两个端点不是对踵点，则必有一组同旁内角之和大于180°。
 　　再观察图2。因为有一组同旁内角之和大于180°，所以这两个角中必有一个角大于90°（不妨设∠ABE>90°）。这种情况下显然有AE>BE，因此BE不是最远距离点对。也就是说，不是对踵点的点对一定不是最远距离点对，所以最远距离点对一定是对踵点。
　　很显然地，过一对对踵点一定可以作两条平行线，使凸包的一条边落在一条直线上。因此，我们设两个指针，一条指向凸包的某条边，另一个指针指向离这条边最远的点。这条边的两个端点与这个点都是对踵点，因此都可能是最远距离点对。按顺序移动边指针并相应地移动点指针，当两个指针绕凸包转了一圈以后，答案就出来了。 
[/quote]

对于这个方法我搞不清楚他如何快速得到“指向离这条边最远的点”

@太没劲了, 13
好方法：）
第一次找最远点是O(n)的，以后继续找的开销是O(1)的。

我昨天看到凯凯的“秃子”算法时，晚上就想出了上面的找点的方法...不过没有给出数学上的证明。


问一下：“秃子”算法如何处理过分的数据，以避免大的复杂度？

@iAkiak

[quote]第一次找最远点是O(n)的，以后继续找的开销是O(1)的。[/quote]

能不能把代码贴上来？如果一侧是一个短边接个大长边，所对的是一批短边，这时继续找的开销能达到 O(1)？另外一个简单问题也顺带问下，你是如何计算点到边的距离？

@sarrow, 15
> 问一下：“秃子”算法如何处理过分的数据，以避免大的复杂度？
如何过分？

@太没劲了, 16
我没写过...
因为是凸多边形，总有一个或多个（此时出现平行边）点到指定边距离最大。
而它的两侧的边与指定边的方向恰好一个更大一个更小。于是不必求点到直线的距离，只需要判断矢量叉积的符号即可。
因为某一边的对应最远点一定在顺时针方向下一边对应点的顺时针方向之后。所以对某条边最远的点的计算也许会有多个，但对所有边的总和来说，也只需要判断总数n个顶点。相对O(n)次边来说，则每次找点就只有O(1)了。

btw.点到直线距离可以解方程。

谢谢 @iAkiak 的回复，下面

[quote]
所以对某条边最远的点的计算也许会有多个，但对所有边的总和来说，也只需要判断总数n个顶点。相对O(n)次边来说，则每次找点就只有O(1)了。
[/quote]

我后来也想到了，就是局部看不是 O(1)，但整个下来就是 O(1)，不过还是感觉有点晕，因为点和线数目一样，某条线导致 bypass 了几个点，那后来怎么给补回来，还是就忽略掉一些线，或者重复检查某些点（就按照线的终点不重复整个的起始线的起始点来结束）。

[quote]点到直线距离可以解方程[/quote]

具体解这个方程的代价如何？俺是好久没搞数学上的这些东西了，有点畏惧感

就当作大一点点的O(1)好了。没有迭代，只有几个分支。