uva 10173 凸包最小覆盖矩形面积

              题意：求凸包的最小覆盖矩形面积

            

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define Maxn 1001+10
#define sqr(x) ((x)*(x))
#define min(a,b) a<b?a:b

using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);

int dcmp(double x)
{
    if(x<-eps) return -1;
    else return x>eps;
}
struct cpoint
{
    double x,y;
    cpoint () {}
    cpoint (double x,double y) :x(x),y(y) {}
    cpoint operator - (const cpoint &u) const {
        return cpoint(x-u.x,y-u.y);
    }
    double operator * (const cpoint &u) const {
        return x*u.y-y*u.x;
    }
    double operator ^ (const cpoint &u) const {
        return x*u.x+y*u.y;
    }
    bool operator == (const cpoint &u) const {
        return dcmp(x-u.x)==0&&dcmp(y-u.y)==0;
    }
};
double dis(cpoint p,cpoint q)
{
    return sqrt(sqr(p.x-q.x)+sqr(p.y-q.y));
}
double dissqr(cpoint p,cpoint q)
{
    return sqr(p.x-q.x)+sqr(p.y-q.y);
}
double cross(cpoint o,cpoint p,cpoint q)
{
    return (p-o)*(q-o);
}
double dot(cpoint o,cpoint p,cpoint q)
{
    return (p-o)^(q-o);
}
cpoint bp;
int cmp(const cpoint &p1,const cpoint &p2)
{
    int u=dcmp(cross(bp,p1,p2));
    return u>0||(u==0&&dcmp(dissqr(bp,p1)-dissqr(bp,p2))<0);
}
void graham(cpoint pin[],int n,cpoint ch[],int &m)
{
    int i,k,j,u,v;
    memcpy(ch,pin,n*sizeof(cpoint));
    for(i=k=0;i<n;i++)
    {
        u=dcmp(ch[i].x-ch[k].x);
        v=dcmp(ch[i].y-ch[k].y);
        if(v<0||(v==0&&u<0)) k=i;
    }
    bp=ch[k];
    sort(ch,ch+n,cmp);
    n=unique(ch,ch+n)-ch;
    if(n<=1) { m=n;return ;}
    if(dcmp(cross(ch[0],ch[1],ch[n-1]))==0)
    {
        m=2;ch[1]=ch[n-1];return ;
    }
    ch[n++]=ch[0];
    for(i=1,j=2;j<n;++j)
    {
        while(i>0&&dcmp(cross(ch[i-1],ch[i],ch[j]))<=0) --i;
        ch[++i]=ch[j];
    }
    m=i;
}
void rotating(cpoint ch[],int m)
{
     int p=1,q=1,r;
     double area=1e99;
     ch[m]=ch[0];
     if(m<3)
       {
           printf("0.0000\n");
           return ;
       }
     for(int i=0;i<m;i++)
      {
          while(dcmp(cross(ch[i],ch[i+1],ch[q+1])-cross(ch[i],ch[i+1],ch[q]))>0)
               q=(q+1)%m;
          while(dcmp(dot(ch[i],ch[i+1],ch[p+1])-dot(ch[i],ch[i+1],ch[p]))>0)
               p=(p+1)%m;
          if(i==0) r=p;
          while(dcmp(dot(ch[i],ch[i+1],ch[r+1])-dot(ch[i],ch[i+1],ch[r]))<=0)
               r=(r+1)%m;
          double d=dissqr(ch[i],ch[i+1]);
          area=min(area,cross(ch[i],ch[i+1],ch[q])*(dot(ch[i],ch[i+1],ch[p])-dot(ch[i],ch[i+1],ch[r]))/d);
      }
    printf("%.4lf\n",area);
}
cpoint ch[Maxn],cp[Maxn];
int n,m;
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
       if(n==0) break;
       for(int i=0;i<n;i++)
         scanf("%lf %lf",&cp[i].x,&cp[i].y);
       graham(cp,n,ch,m);
       rotating(ch,m);
   }
   return 0;
}