l******y
发帖数: 472 | 1 给定n个点（xi, yi)，求一条直线ax+by =c（即找出a,b,c)，使得max（｜a*xi +b*yi
-c｜）（1≤ i ≤n)的值最小。 因为要求的是直线，所以a，b不能同时为0。
我的想法是先求出这些点的闭包，然后对于闭包中的每条线段，确定一条过
这条线段两端点的直线，然后找到离这条直线最远的点，再做一条平行于该直线的直线，
这样所有的点就都在这两条直线之间。这两条直线的距离记为d，找到使d最小的那两条直
线（尝试凸包中所有的线段），然后再做一条直线，使其平行于这两条直线，并且到这两
条直线的距离相等，则这条直线就是我们要求的。暂时还没法证明。谁能证明我的想法对
的或是错的么，或者有其它idea？thanks | c**********t
发帖数: 98 | 2 怎么觉得（0，0，0）是解呢？是题目错了，还是我理解错了？ | l*********r
发帖数: 674 | 3 是不是找到距离最远的(xi, yi)和(xj, yj)，然后做他们的垂直平分线？ | l******y
发帖数: 472 | 4
刚才忘了一点，求的是一条直线，a，b不能同时为0
【在 c**********t 的大作中提到】
: 怎么觉得（0，0，0）是解呢？是题目错了，还是我理解错了？
| l******y
发帖数: 472 | 5
你这个想法和我上面说的有点相似，不过我不确定我的想法是否正确
【在 l*********r 的大作中提到】
: 是不是找到距离最远的(xi, yi)和(xj, yj)，然后做他们的垂直平分线？
|
|
