来自方一鸣的问题
给你n个点,n很大,定义距离为D(A,B)=|x1-x2|+|y1-y2|,找出这么多点的连线的最长距离,求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
给你n个点,n很大,定义距离为D(A,B)=|x1-x2|+|y1-y2|,找出这么多点的连线的最长距离,
求算法或思路,给代码最好,注意,用遍历不可行,就是算出所有线的距离的算法不可行,时间太长
这个题的基本方法是：求出点集的凸包,对凸包上的所有点进行O(n^2)的枚举即可.关键在于凸包的求法,下面我简单介绍一下LRJ极力推荐的凸包求法.首先将所有点按X轴排序,不难证明最左和最右的两个一定在凸包上,于是一张两...
大家都在问
最新问答
海冰含盐量接近淡水，...2020-12-30
三峡游山峰一下子就被...2020-12-30
二元一次方程简单的配...2020-12-30
【偏裨将校是什么意思...2020-12-30
如图秒表的读数为__...2020-12-30
____abigfi...2020-12-30
【知道本金和税后利息...2020-12-30
《一百条裙子》读后感...2020-12-30
利用矩阵解二元一次方...2020-12-30
【英语中的peasa...2020-12-30