uva 11168
题意：给出平面上的n个点，求一条直线，使得所有点在该直线的同一侧且所有点到该直线的距离和最小，输出该距离和。
思路：要使所有点在该直线的同一侧，明显是直接利用凸包的边更优。所以枚举凸包的没条边，然后求距离和。直线一般式为Ax + By + C = 0.点(x0, y0)到直线的距离为 fabs(Ax0+By0+C)/sqrt(A*A+B*B).由于所有点在直线的同一侧，那么对于所有点，他们的(Ax0+By0+C)符号相同，显然可以累加出sumX和sumY，然后统一求和。
水。。。。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 #include<memory.h> 7 #include<cstdlib> 8 #include<vector> 9 #define clc(a,b) memset(a,b,sizeof(a)) 10 #define LL long long int 11 #define up(i,x,y) for(i=x;i<=y;i++) 12 #define w(a) while(a) 13 using namespace std; 14 const double inf=0x3f3f3f3f; 15 const int N = 4010; 16 const double eps = 5*1e-13; 17 const double PI = acos(-1.0); 18 19 double torad(double deg) 20 { 21 return deg/180 * PI; 22 } 23 24 struct Point 25 { 26 double x, y; 27 Point(double x=0, double y=0):x(x),y(y) { } 28 }; 29 30 typedef Point Vector; 31 32 Vector operator + (const Vector& A, const Vector& B) 33 { 34 return Vector(A.x+B.x, A.y+B.y); 35 } 36 Vector operator - (const Point& A, const Point& B) 37 { 38 return Vector(A.x-B.x, A.y-B.y); 39 } 40 double Cross(const Vector& A, const Vector& B) 41 { 42 return A.x*B.y - A.y*B.x; 43 } 44 45 Vector Rotate(const Vector& A, double rad) 46 { 47 return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad)); 48 } 49 50 bool operator < (const Point& p1, const Point& p2) 51 { 52 return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); 53 } 54 55 bool operator == (const Point& p1, const Point& p2) 56 { 57 return p1.x == p2.x && p1.y == p2.y; 58 } 59 60 // 点集凸包 61 // 如果不希望在凸包的边上有输入点，把两个 <= 改成 < 62 // 如果不介意点集被修改，可以改成传递引用 63 vector<Point> ConvexHull(vector<Point> p) 64 { 65 // 预处理，删除重复点 66 sort(p.begin(), p.end()); 67 p.erase(unique(p.begin(), p.end()), p.end()); 68 69 int n = p.size(); 70 int m = 0; 71 vector<Point> ch(n+1); 72 for(int i = 0; i < n; i++) 73 { 74 while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; 75 ch[m++] = p[i]; 76 } 77 int k = m; 78 for(int i = n-2; i >= 0; i--) 79 { 80 while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; 81 ch[m++] = p[i]; 82 } 83 if(n > 1) m--; 84 ch.resize(m); 85 return ch; 86 } 87 88 // 过两点p1, p2的直线一般方程ax+by+c=0 89 // (x2-x1)(y-y1) = (y2-y1)(x-x1) 90 void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c) { 91 a = p2.y-p1.y; 92 b = p1.x-p2.x; 93 c = -a*p1.x - b*p1.y; 94 } 95 96 int main() 97 { 98 int t,n; 99 double x,y; 100 double sumx,sumy; 101 double ans; 102 int cas=1; 103 scanf("%d",&t); 104 while(t--) 105 { 106 scanf("%d",&n); 107 vector<Point>p; 108 sumx=0;sumy=0; 109 for(int i=0;i<n;i++) 110 { 111 scanf("%lf%lf",&x,&y); 112 sumx+=x;sumy+=y; 113 p.push_back(Point(x,y)); 114 } 115 vector<Point>ch=ConvexHull(p); 116 ans=inf; 117 int edge=ch.size(); 118 if(edge<=2) 119 { 120 ans=0; 121 } 122 else 123 { 124 for(int i=0;i<edge;i++) 125 { 126 double a,b,c; 127 getLineGeneralEquation(ch[i],ch[(i+1)%edge],a,b,c); 128 ans=min(ans,fabs(sumx*a+sumy*b+n*c)/sqrt(a*a+b*b)); 129 } 130 } 131 printf("Case #%d: %.3f ",cas++,ans/n); 132 } 133 return 0; 134 }