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

``` 1 #include <iostream>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <stdio.h>
5 #include <time.h>
6 #include <math.h>
7
8 #define N 1005
9 #define eps 1e-8     //搜索停止条件阀值
10 #define INF 1e99
11 #define delta 0.98   //温度下降速度
12 #define T 100        //初始温度
13
14 using namespace std;
15
16 int dx[4] = {0, 0, -1, 1};
17 int dy[4] = {-1, 1, 0, 0};  //上下左右四个方向
18
19 struct Point
20 {
21     double x, y;
22 };
23
24 Point s[N], t[N];
25
26 double cross(Point A, Point B, Point C)
27 {
28     return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
29 }
30
31 double multi(Point A, Point B, Point C)
32 {
33     return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);
34 }
35
36 double dist(Point A, Point B)
37 {
38     return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
39 }
40
41 double GetDist(Point A, Point B, Point C)
42 {
43     if(dist(A, B) < eps) return dist(B, C);
44     if(multi(A, B, C) < -eps) return dist(A, C);
45     if(multi(B, A, C) < -eps) return dist(B, C);
46     return fabs(cross(A, B, C) / dist(A, B));
47 }
48
49 double GetSum(Point s[], Point t[], int n, Point o)
50 {
51     double ans = 0;
52     while(n--)
53         ans += GetDist(s[n], t[n], o);
54     return ans;
55 }
56
57 double Search(Point s[], Point t[], int n, Point &o)
58 {
59     o = s[0];
60     double tem = T;
61     double ans = INF;
62     while(tem > eps)
63     {
64         bool flag = 1;
65         while(flag)
66         {
67             flag = 0;
68             for(int i = 0; i < 4; i++)    //上下左右四个方向
69             {
70                 Point z;
71                 z.x = o.x + dx[i] * tem;
72                 z.y = o.y + dy[i] * tem;
73                 double tp = GetSum(s, t, n, z);
74                 if(ans > tp)
75                 {
76                     ans = tp;
77                     o = z;
78                     flag = 1;
79                 }
80             }
81         }
82         tem *= delta;
83     }
84     return ans;
85 }
86
87 int main()
88 {
89     int n;
90     while(scanf("%d", &n) != EOF)
91     {
92         for(int i = 0; i < n; i++)
93             scanf("%lf %lf %lf %lf", &s[i].x, &s[i].y, &t[i].x, &t[i].y);
94         Point o;
95         double ans = Search(s, t, n, o);
96         printf("%.1lf %.1lf %.1lf\n", o.x, o.y, ans);
97     }
98     return 0;
99 }  ```

780 篇文章62 人订阅

0 条评论

## 相关文章

3294

962

1294

### 【Leetcode】81. 搜索旋转排序数组 II

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1652

1062

2172

4946

20310

4137

2247