给你n个点,n很大,定义距离为D(A,B)= |x1 -x2| + |y1 - y2| ,找出这么多点的连线的最长距离,

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/19 06:53:51

给你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.

已知点A（x1,y1),B(x2,y2),将AB之间的距离记为AB的绝对值. 设两点坐标为（x1,y1)(x2,y2) 则两点间的距离公式 d=√[(x1-x2)^2+(y1-y2)^2],这是怎么已知点A（x1，y1），B（x2，y2），将A、B之间的距离记作|AB|．求两点A（x1,y1) B(x2,y2) 求A、B两点之间的距离公式若A（x1，y1），B（x2，y2）为一次函数y=3x-1的图象上的两个不同的点，且x1x2≠0，设M＝y1+1x1，N 已知3个点坐标A（x1,y1,z1）,B(x2,y2,z2),C(x3,y3,z3),以及A到D点距离T1,B到D点距离 ①圆的直径式方程：以点A(x1,y1),B(x2,y2)的连线段为直径的圆的方程是：直线y=3x+2 上有P1(x1,y1),P2(x2,y2).Pn(Xn,Yn)这n个点,若他们横坐标的标准差为8.5, 为什么高等数学里N维空间的两点距离公式为根号下（x1-y1）^2+（x2-y2）^2+.+(xn-yn)^2, 已知点A(x1,y1),B(x2,y2),记OA=(x1,y1),OB(x2,y2),定义运算OA·OB=x1x2+y1 已知点A(x1,y1),B(X2,y2)在斜率为k的直线上,若丨AB丨=a,则丨y2-y1丨等于直角坐标上有两点A（X1,Y1）,B（X2,Y2）,求AB的距离,有什么公式?