给你n个点,n很大,定义距离为D(A,B)= |x1 -x2| + |y1 - y2| ,找出这么多点的连线的最长距离,求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/15 14:46:09
给你n个点,n很大,定义距离为D(A,B)= |x1 -x2| + |y1 - y2| ,找出这么多点的连线的最长距离,求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
给你n个点,n很大,定义距离为D(A,B)= |x1 -x2| + |y1 - y2| ,找出这么多点的连线的最长距离,
求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
给你n个点,n很大,定义距离为D(A,B)= |x1 -x2| + |y1 - y2| ,找出这么多点的连线的最长距离,求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
这个题的基本方法是：求出点集的凸包,对凸包上的所有点进行O(n^2)的枚举即可.关键在于凸包的求法,下面我简单介绍一下LRJ极力推荐的凸包求法.
首先将所有点按X轴排序,不难证明最左和最右的两个一定在凸包上,于是一张两个点分别为起点和终点,求一次上凸包和一次下凸包即可.求上凸包时,用到了栈结构,首先将最左节点入栈,然后各点依次入栈,同时随时检查位于栈顶的三个点组成图形是否为凸（用叉积或有向面积均可）,否则将栈内第二个元素出栈.这样最后栈内元素即位上凸包,下凸包自然是类似的啦.代码如下：
const lim=30001;
type point=record
x,y:longint;
end;
var a:array[1..lim+1] of point;
us,ds:array[1..lim+1] of longint;
n,i,j,topu,topd:longint;
max:extended;
procedure qs(s,t:longint);
var i,j:longint;
k:point;
begin
if smax then
max:=sqr(a[us[i]].x-a[ds[j]].x)+sqr(a[us[i]].y-a[ds[j]].y);
writeln(sqrt(max):0:2);
until seekeof;
end.