首页 > 代码库 > UVa 11168 (凸包+点到直线距离) Airport
UVa 11168 (凸包+点到直线距离) Airport
题意：
平面上有n个点，求一条直线使得所有点都在直线的同一侧。并求这些点到直线的距离之和的最小值。
分析：
只要直线不穿过凸包，就满足第一个条件。要使距离和最小，那直线一定在凸包的边上。所以求出凸包以后，枚举每个边求出所有点到直线的距离之和得到最小值。
点到直线距离公式为：
因为点都在直线同一侧，所以我们可以把加法“挪”到里面去，最后再求绝对值，所以可以预处理所有点的横坐标之和与纵坐标之和。当然常数C也要记得乘上n倍。
已知两点坐标求过该点直线的方程，这很好求不再赘述，考虑到直线没有斜率的情况，最终要把表达式中的分母乘过去。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 using namespace std; 8 9 struct Point 10 { 11 double x, y; 12 Point(double x=0, double y=0):x(x), y(y) {} 13 }; 14 typedef Point Vector; 15 Point operator + (Point A, Point B) 16 { 17 return Point(A.x+B.x, A.y+B.y); 18 } 19 Point operator - (Point A, Point B) 20 { 21 return Point(A.x-B.x, A.y-B.y); 22 } 23 bool operator < (const Point& A, const Point& B) 24 { 25 return A.x < B.x || (A.x == B.x && A.y < B.y); 26 } 27 bool operator == (const Point& A, const Point& B) 28 { 29 return A.x == B.x && A.y == B.y; 30 } 31 double Cross(Vector A, Vector B) 32 { 33 return A.x*B.y - A.y*B.x; 34 } 35 36 vector<Point> ConvexHull(vector<Point> p) { 37 // 预处理，删除重复点 38 sort(p.begin(), p.end()); 39 p.erase(unique(p.begin(), p.end()), p.end()); 40 41 int n = p.size(); 42 int m = 0; 43 vector<Point> ch(n+1); 44 for(int i = 0; i < n; i++) { 45 while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; 46 ch[m++] = p[i]; 47 } 48 int k = m; 49 for(int i = n-2; i >= 0; i--) { 50 while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; 51 ch[m++] = p[i]; 52 } 53 if(n > 1) m--; 54 //for(int i = 0; i < m; ++i) printf("%lf %lf\n", ch[i].x, ch[i].y); 55 ch.resize(m); 56 return ch; 57 } 58 59 double sumx, sumy; 60 61 double Dist(Point a, Point b, int m) 62 { 63 double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y; 64 //printf("%lf %lf", fabs(A*sumx+B*sumy+C), sqrt(A*A+B*B)); 65 return (fabs(A*sumx+B*sumy+C*m) / sqrt(A*A+B*B)); 66 } 67 68 int main(void) 69 { 70 #ifdef LOCAL 71 freopen("11168in.txt", "r", stdin); 72 #endif 73 74 int T; 75 scanf("%d", &T); 76 for(int kase = 1; kase <= T; ++kase) 77 { 78 int n; 79 vector<Point> p; 80 sumx = 0.0, sumy = 0.0; 81 scanf("%d", &n); 82 for(int i = 0; i < n; ++i) 83 { 84 double x, y; 85 scanf("%lf%lf", &x, &y); 86 p.push_back(Point(x, y)); 87 sumx += x; sumy += y; 88 } 89 vector<Point> ch = ConvexHull(p); 90 int m = ch.size(); 91 //for(int i = 0; i < m; ++i) printf("%lf %lf\n", ch[i].x, ch[i].y); 92 if(m <= 2) 93 { 94 printf("Case #%d: 0.000\n", kase); 95 continue; 96 } 97 98 double ans = 1e10; 99 for(int i = 0; i < m; ++i)100 ans = min(ans, Dist(ch[i], ch[(i+1)%m], n));101 printf("Case #%d: %.3lf\n", kase, ans/n);102 }103 }
UVa 11168 (凸包+点到直线距离) Airport
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。