UVA 11168 Airport（凸包+直线方程）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34780

【思路】

凸包+直线方程。

求出点集的凸包，则题目所求直线必在凸包的边上。

如果已知边的直线表达式为Ax+By+C，则距离和为：

直线两点式为：

简单化化就可以搞出一般式了。

【代码】

 1 #include<cmath>
 2 #include<vector>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const double eps = 1e-10;
 8 int dcmp(double x) {
 9     if(fabs(x)<eps) return 0; else return x<0? -1:1;
10 }
11 
12 struct Pt {
13     double x,y;
14     Pt(double x=0,double y=0):x(x),y(y) {};
15 };
16 typedef Pt vec;
17 vec operator - (Pt A,Pt B) { return vec(A.x-B.x,A.y-B.y); }
18 bool operator == (Pt A,Pt B) {
19     return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;
20 }
21 bool operator < (const Pt& a,const Pt& b) {
22     return a.x<b.x || (a.x==b.x && a.y<b.y);
23 }
24 double cross(Pt A,Pt B) { return A.x*B.y-A.y*B.x; }
25 
26 int n;
27 vector<Pt> ConvexHull(vector<Pt> p) {
28     sort(p.begin(),p.end());
29     p.erase(unique(p.begin(),p.end()),p.end());
30     vector<Pt> ch(n+1);
31     int n=p.size();
32     int m=0;
33     for(int i=0;i<n;i++) {
34         while(m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
35         ch[m++]=p[i];
36     }
37     int k=m;
38     for(int i=n-2;i>=0;i--) {
39         while(m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
40         ch[m++]=p[i];
41     }
42     if(n>1) m--;
43     ch.resize(m);
44     return ch;
45 }
46 
47 void getLineEquation(Pt a,Pt b,double& A,double& B,double& C) {
48     A=b.y-a.y; B=a.x-b.x;
49     C=-a.x*A - a.y*B;
50 }
51 
52 int main() {
53     int T,kase=0;
54     scanf("%d",&T);
55     while(T--) {
56         scanf("%d",&n);
57         vector<Pt> P,ch;
58         double x,y,sx=0,sy=0,A,B,C;
59         for(int i=0;i<n;i++) {
60             scanf("%lf%lf",&x,&y);
61             sx+=x , sy+=y;
62             P.push_back(Pt(x,y));
63         }
64         ch=ConvexHull(P);
65         double ans=1e15;
66         if(ch.size()<=2) ans=0;
67         for(int i=0;i<ch.size();i++) {
68             getLineEquation(ch[i],ch[(i+1)%ch.size()],A,B,C);
69             double res=fabs((A*sx+B*sy+C*n)/(sqrt(A*A+B*B)));
70             if(res<ans) ans=res;
71         }
72         printf("Case #%d: %.3lf
",++kase,ans/n);
73     }
74     return 0;
75 }