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

题目:平面上给定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 }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

详解Python列表推导式

列表推导式,也叫列表解析式,英文名称为list comprehension,可以使用非常简洁的方式来快速生成满足特定需求的列表,代码具有非常强的可读性。另外,P...

3294
来自专栏尾尾部落

[剑指offer] 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

962
来自专栏前端吧啦吧啦

数据结构(二)之算法基础

1294
来自专栏Leetcode名企之路

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

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

1652
来自专栏desperate633

LintCode 搜索旋转排序数组题目分析代码

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值...

1062
来自专栏Petrichor的专栏

numpy: np.random模块 探究(源码)

2172
来自专栏Python小屋

使用Python列表实现向量运算

在Python中,列表支持与整数的乘法运算,但表示的是列表元素的重复,并生成新列表,如: >>> [1,2,3]*3 [1, 2, 3, 1, 2, 3, 1...

4946
来自专栏猿人谷

memmove函数

写一个函数,完成内存之间的拷贝 void* mymemcpy( void *dest, const void *src, size_t count )   { ...

20310
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

4137
来自专栏章鱼的慢慢技术路

求 pi 的近似值题型汇总

2247

扫码关注云+社区

领取腾讯云代金券