UVa 11168 Airport

这个月看看计算几何，这道题写的代码出现的问题还是挺多的，不过索性最后解决了。

题意：给出平面上n个点，找一条直线，使得所有点在直线的同侧（也可以在直线上），且到直线上的距离之和尽量小。

思路：计算几何凸包求出包含所有点的多边形，那么所求直线即多边形其中一条边，这里涉及一个优化除该边之外所有点到边的距离，因为所有点在直线一侧，求出所有点的x坐标之和还有y坐标之和，用一般式解决，算法时间O(1)，接下来就是遍历所有边了算法时间O(n).

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
struct Point
{
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector ;
Vector operator + (const Vector& a, const Vector& b) {
    return Vector(a.x+b.x, a.y+b.y);
}
Vector operator - (const Vector& a, const Vector& b) {
    return Vector(a.x-b.x, a.y-b.y);
}
Vector operator * (const Vector& a, double p) {
    return Vector(a.x*p, a.y*p);
}
Vector operator / (const Vector& a, double p) {
    return Vector(a.x/p, a.y/p);
}
bool operator < (const Point& p1, const Point& p2){
    return p1.x<p2.x ||(p1.x==p2.x&&p1.y<p2.y);
}
bool operator == (const Point& p1, const Point& p2){
    return p1.x == p2.x && p1.y == p2.y;
}
double Cross(Vector A,Vector B) { return A.x*B.y - A.y*B.x;}
Point GLI(Point P,Vector v,Point Q,Vector w)
{
  Vector u=P-Q;
  double t=Cross(w,u)/Cross(v,w);
  return P+v*t;
}

int Andrew(Point *p,int n,Point *q)
{
  sort(p,p+n);
  int m=0;
  for(int i=0;i<n;i++)
  {
    while(m>1&&Cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0) m--;
    q[m++]=p[i];
  }
  int k=m;
  for(int i=n-2;i>=0;i--)
  {
    while(m>k&&Cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0) m--;
    q[m++]=p[i];
  }
  if(n>1) m--;
  return m;
}
const int maxn=10005;
Point q[maxn];
int main()
{
  int T,n,Case=1;double x,y;
  cin>>T;
  while(T--)
  {
    cin>>n;Point p[maxn];
    double xx=0,yy=0;
    for(int i=0;i<n;i++)
    {
      cin>>x>>y;
      p[i].x=x;p[i].y=y;
      xx+=x;yy+=y;
    }
    int m=Andrew(p,n,q);
    q[m]=q[0];
    /*for(int i=0;i<m;i++)
    {
      printf("^%f %f\n",q[i].x,q[i].y);
    }*/
    double ans=INF;
    //printf("#%f %f\n",xx,yy);
    for(int i=0;i<m;i++)
    {
      //i=(i+1)%m;
      //int x0=(xx-q[i].x-q[i+1].x);
      //int y0=(yy-q[i].y-q[i+1].y);
      double A=(q[i].y-q[i+1].y);
      double B=q[i+1].x-q[i].x;
      double C=(q[i+1].y*q[i].x-q[i].y*q[i+1].x);
      //printf("%f,%f,%f\n",A,B,C);
      ans=min(ans,fabs(A*xx+B*yy+C*n)/sqrt(A*A+B*B));
    }
    printf("Case #%d: ",Case++);
    if(n<=2) printf("0.000\n");
    else
    printf("%.3f\n",ans/n);
    //Q.erase();
  }
}