平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。

题目：平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。

源码如下：

 #include <iostream>

 #include <string.h>

 #include <stdlib.h>

 #include <stdio.h>

 #include <time.h>

 #include <math.h>  

 #define N 1005

 #define eps 1e-8     //搜索停止条件阀值

 #define INF 1e99

 #define delta 0.98   //温度下降速度

 #define T 100        //初始温度  

 using namespace std;  

 int dx[] = {, , -, };

 int dy[] = {-, , , };  //上下左右四个方向  

 struct Point

 {

     double x, y;

 };  

 Point s[N], t[N];  

 double cross(Point A, Point B, Point C)

 {

     return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);

 }    

 double multi(Point A, Point B, Point C)

 {

     return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);

 }    

 double dist(Point A, Point B)

 {

     return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));

 }  

 double GetDist(Point A, Point B, Point C)

 {

     if(dist(A, B) < eps) return dist(B, C);

     if(multi(A, B, C) < -eps) return dist(A, C);

     if(multi(B, A, C) < -eps) return dist(B, C);

     return fabs(cross(A, B, C) / dist(A, B));

 }    

 double GetSum(Point s[], Point t[], int n, Point o)

 {

     double ans = ;

     while(n--)

         ans += GetDist(s[n], t[n], o);

     return ans;

 }  

 double Search(Point s[], Point t[], int n, Point &o)

 {

     o = s[];

     double tem = T;

     double ans = INF;

     while(tem > eps)

     {

         bool flag = ;

         while(flag)

         {

             flag = ;

             for(int i = ; i < ; i++)    //上下左右四个方向

             {

                 Point z;

                 z.x = o.x + dx[i] * tem;

                 z.y = o.y + dy[i] * tem;

                 double tp = GetSum(s, t, n, z);

                 if(ans > tp)

                 {

                     ans = tp;

                     o = z;

                     flag = ;

                 }

             }

         }

         tem *= delta;

     }

     return ans;

 }  

 int main()

 {

     int n;

     while(scanf("%d", &n) != EOF)

     {

         for(int i = ; i < n; i++)

             scanf("%lf %lf %lf %lf", &s[i].x, &s[i].y, &t[i].x, &t[i].y);

         Point o;

         double ans = Search(s, t, n, o);

         printf("%.1lf %.1lf %.1lf\n", o.x, o.y, ans);

     }

     return ;

 }  

平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。的相关教程结束。