本文共 2875 字，大约阅读时间需要 9 分钟。

原文地址：

已知一个点集合和一条直线ax+by+c = 0，我们要在直线上找到一个点，这个点到这个集合的每个点的距离和是最小的。

例子：

上图中直线x - y - 3 = 0的最优点是(2, -1)，这个点与其他点的总距离是20.77，也就是最小的总距离啦。

如果我们在这条直线的无限远位置上取一个点，那么总距离也是无限大的，现在当我们朝着已知的点集合的方向移动这个线上的点，一定时间以后，这个距离和就会开始下降，当这个点朝直线上另外一个无限远的地方移动的时候，那么这个距离和就又开始增加了。所以这个距离的曲线像一个U型曲线，我们要找的是这个U型曲线最底部的值。

因为U型曲线不是单调递增或者单调递减，所以我们不能通过二分查询来找到最底部的值，在这里呢，我们将用三分搜索来找到最底部的值。三分搜索在每一次迭代中都会跳过三分之一的搜索空间，可以看看三分查询具体是什么。

下面是解决方案，我们用low和high分别为初始化为最小值和最大值，然后开始迭代，在每一次迭代中我们都要计算两个中间值：mid1与mid2，这个两个值分别表示搜索空间的1/3与2/3处的位置。我们用mid1与mid2计算所有点的总距离，并通过比较这些距离来更新low和high，这个迭代一直将进行到low与high大致相等。

//  C/C++ program to find optimum location and total cost#include 
   
    using namespace std;#define sq(x) ((x)*(x))#define EPS 1e-6#define N 5//  structure defining a pointstruct point{    int x, y;    point()  {}    point(int x, int y) : x(x), y(y)   {}};//  structure defining a line of ax + by + c = 0 formstruct line{    int a, b, c;    line(int a, int b, int c) : a(a), b(b), c(c) {}};//  method to get distance of point (x, y) from point pdouble dist(double x, double y, point p){    return sqrt(sq(x - p.x) + sq(y - p.y));}/*  Utility method to compute total distance all points    when choose point on given line has x-cordinate    value as X   */double compute(point p[], int n, line l, double X){    double res = 0;    //  calculating Y of choosen point by line equation    double Y = -1 * (l.c + l.a*X) / l.b;    for (int i = 0; i < n; i++)        res += dist(X, Y, p[i]);    return res;}//  Utility method to find minimum total distancedouble findOptimumCostUtil(point p[], int n, line l){    double low = -1e6;    double high = 1e6;    // loop untill difference between low and high    // become less than EPS    while ((high - low) > EPS)    {        // mid1 and mid2 are representative x co-ordiantes        // of search space        double mid1 = low + (high - low) / 3;        double mid2 = high - (high - low) / 3;        //        double dist1 = compute(p, n, l, mid1);        double dist2 = compute(p, n, l, mid2);        // if mid2 point gives more total distance,        // skip third part        if (dist1 < dist2)            high = mid2;        // if mid1 point gives more total distance,        // skip first part        else            low = mid1;    }    // compute optimum distance cost by sending average    // of low and high as X    return compute(p, n, l, (low + high) / 2);}//  method to find optimum costdouble findOptimumCost(int points[N][2], line l){    point p[N];    //  converting 2D array input to point array    for (int i = 0; i < N; i++)        p[i] = point(points[i][0], points[i][1]);    return findOptimumCostUtil(p, N, l);}//  Driver code to test above methodint main(){    line l(1, -1, -3);    int points[N][2] = {
  {-3, -2}, {-1, 0}, {-1, 2},                                   {
  1, 2}, {
  3, 4}};    cout << findOptimumCost(points, l) << endl;    return 0;}
   

输出：

20.7562