點擊打開鏈接

?

Problem D
Airport
Input: Standard Input

Output: Standard Output

?

It is no coincidence? that in no known language ? does the phrase 'As pretty as an Airport' appear.

Douglas Adams

There is a small town with n houses. The town needs an airport. An airport is basically a very long, very straight road. Think of it as an infinite line. We need to build the airport such that the average distance from each house to the airport is as small as possible. However, no one wants to walk across the runway, so all of the houses must be on the same side of the airport. (Some houses may be a distance of zero away from the runway, but that's ok; we'll give them some free ear plugs.)

Where should we build the airport, and what will be the average distance?

Input

The first line of input gives the number of cases, N (<=65) .N test cases follow. Each one is a line containing n (0<? n <= 10000) , followed by n lines giving the xy-coordinates of the houses. All coordinates are integers with absolute value of at most 80,000 .

?

Output

For each test case, output one line containing "Case #x:" followed by the average distance from the airport to the houses, with 3 digits after the decimal point. No answer will be within 10^-5 of a round-off error case.

?

Sample Input???????????????????????????? Output for Sample Input

?

4 4 0 0 0 1 1 0 1 1 2 15035 39572 34582 39535 3 0 0 0 1 1 0 5 0 0 0 2 2 0 2 2 1 1

Case #1: 0.500 Case #2: 0.000 Case #3: 0.236 Case #4: 1.000

?

---

Problemsetters: Igor Naverniouk and Derek Kisman

?

?

題意：給出平面上n個點，找一條直線，使得所有的點在直線的同側（也可以在直線上），且到直線的距離之和盡量小。

A了一天，WA了十多次，終于過了。不容易啊。要選擇這么一條直線，不難發現，選擇凸包的邊所在的直線是最優。由于凸包上的邊不超過n條，則只需O（n)時間就會解決這個問題。設直線的一般式方程為Ax+By+C=0,則點（x0,y0)到直線的距離是為：|Ax0+By0+C|/sqrt(A^2+B^2)。因為所有的點在同一側，所有的點的正負號相同。這樣我們先處理所有點的x坐標和y坐標之和。首先要注意定義無窮大的時候不能定義成999999，如果這樣會是WA。而要定義成0x3f3f3f3f。然后要注意unique的使用，要去重。

?

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double inf=0x3f3f3f3f; int n; double sumx,sumy; const double eps = 1e-10; struct Point {double x,y;Point(double x=0,double y=0):x(x),y(y){}//構造函數bool operator < (const Point& a) const{if(a.x != x) return x < a.x;return y < a.y;} }; typedef Point Vector; Point P[10010],ch[10010];//向量+向量=向量，點+向量=點 Point operator+(Point A,Point B) {return Point(A.x+B.x,A.y+B.y); }//點-點=向量 Point operator-(Point A,Point B) {return Point(A.x-B.x,A.y-B.y); } int dcmp(double x) {if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } bool operator == (const Point& a, const Point &b) {return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } //就算OA和OB的叉積 double Cross(Point A,Point B) {return A.x*B.y-A.y*B.x; }//凸包 int ConvexHull(Point *p,int n,Point *ch)//ch是空的 {sort(p,p+n);//x按照從小到大排序，若x相等，按照y從小到大排序n=unique(p,p+n)-p;int m=0;for(int i=0;i<n;i++){while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;ch[m++]=p[i];}int k=m;for(int i=n-2;i>=0;i--){while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;ch[m++]=p[i];}if(n>1)m--;return m;//返回的是凸包的頂點數，ch數組存的是凸包的頂點 }//總的點到Ax+By+C的距離 double get(double A,double B,double C) {double k=fabs(A*sumx+B*sumy+n*C);double v=sqrt(A*A+B*B);return k/v; } //Ax+By+C=0 double getDist(Point a,Point b) {double A=a.y-b.y;double B=b.x-a.x;double C=a.x*b.y-a.y*b.x;return get(A,B,C); }int main() {int t,cas=1;scanf("%d",&t);while(t--){sumx=0,sumy=0;double temp,minn=inf;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lf%lf",&P[i].x,&P[i].y);sumx+=P[i].x;sumy+=P[i].y;}printf("Case #%d: ",cas++);if(n<=2){printf("0.000\n");continue;}int m=ConvexHull(P,n,ch);for(int i=0;i<m;i++){//printf("%lf %lf %lf %lf\n",ch[i].x,ch[i].y,ch[i+1].x,ch[i+1].y);temp=getDist(ch[i],ch[(i+1)%m]);//printf("其余點點到i和i+1的距離是：%lf %lf\n",temp,temp/(nn*1.0));minn=min(minn,temp);}double ans=minn/n;printf("%.3lf\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA 11168 - Airport 凸包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。