[ UVA ] 11168 - Airport

題目:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2109

解法:
這題要用解析幾何的方式算點到直線距離。
先求凸包，可以知道最佳直線一定在凸包的邊上，由於所有點在直線的同一側，那麽對於所有點，他們的(Ax0+By0+C)符號相同，根據公式知直線一般式為Ax+By+C=0；點(x0,y0)到直線的距離為:

• fabs(Ax0+By0+C)/sqrt(A*A+B*B)

所以只要先求​​出x的和以及y的和，能在O(1)計算所有距離和。

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

#include<bits/stdc++.h> template<typename T> struct point{ T x,y; point(){} point(const T&dx,const T&dy):x(dx),y(dy){} inline const point operator-(const point &b)const{ return point(x-b.x,y-b.y); } inline const T cross(const point &b)const{ return x*b.y-y*b.x; } }; template<typename T> struct line{ line(){} point<T> p1,p2; T a,b,c;/*ax+by+c=0*/ line(const point<T>&x,const point<T>&y):p1(x),p2(y){} inline void pton(){/*轉成一般式*/ a=p1.y-p2.y; b=p2.x-p1.x; c=-a*p1.x-b*p1.y; } }; template<typename T> struct polygon{ polygon(){} std::vector<point<T> > p; inline const point<T>& operator[](int id)const{ return p[id]; } inline static bool graham_cmp(const point<T>& a,const point<T>& b){ return (a.x<b.x)||(a.x==b.x&&a.y<b.y);/*凸包排序函數*/ } inline void graham(std::vector<point<T> > &s){/*凸包*/ sort(s.begin(),s.end(),graham_cmp); p.resize(s.size()+1); int m=0; for(int i=0;i<(int)s.size();++i){ while(m>=2&&(p[m-1]-p[m-2]).cross(s[i]-p[m-2])<=0)--m; p[m++]=s[i]; } for(int i=s.size()-2,t=m+1;i>=0;--i){ while(m>=t&&(p[m-1]-p[m-2]).cross(s[i]-p[m-2])<=0)--m; p[m++]=s[i]; } if(s.size()>1)--m; p.resize(m); } }; int t,n; std::vector<point<double > >px; polygon<double>p; int main(){ scanf("%d",&t); for(int cnt=1;cnt<=t;++cnt){ scanf("%d",&n); px.resize(n); double ax=0,ay=0; for(int i=0;i<n;++i){ scanf("%lf%lf",&px[i].x,&px[i].y); ax+=px[i].x; ay+=px[i].y; } p.graham(px); double ans=1e9; for(int i=p.p.size()-1,j=0;j<(int)p.p.size();i=j++){ line<double>l(p[i],p[j]); l.pton(); ans=std::min(ans,fabs(l.a*ax+l.b*ay+l.c*n)/sqrt(l.a*l.a+l.b*l.b)); } printf("Case #%d: %.3f\n",cnt,p.p.size()>1?ans/n:0.0); } return 0; }