百度之星初赛1006(计算几何:能包含凸包的最小矩形面积)

#include<stdio.h>
#include<cmath>
#include<algorithm>
#define eps 1e-8
#define N 50010
using namespace std;
struct Point
{double x,y;Point() {}Point(double x0,double y0):x(x0),y(y0) {}
};
Point p[N];
int con[N];
int cn;
int n;
struct Line
{Point a,b;Line() {}Line(Point a0,Point b0):a(a0),b(b0) {}
};
double Xmult(Point o,Point a,Point b)
{return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
double Dmult(Point o,Point a,Point b)
{return (a.x-o.x)*(b.x-o.x)+(a.y-o.y)*(b.y-o.y);
}
int Sig(double a)
{return a<-eps?-1:a>eps;
}
double Dis(Point a,Point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(Point a,Point b)
{double d=Xmult(p[0],a,b);if(d>0)return 1;if(d==0 && Dis(p[0],a)<Dis(p[0],b))return 1;return 0;
}
double min(double a,double b)
{return a<b?a:b;
}
void Graham()
{int i,ind=0;for(i=1; i<n; i++)if(p[ind].y>p[i].y || (p[ind].y==p[i].y) && p[ind].x>p[i].x)ind=i;swap(p[ind],p[0]);sort(p+1,p+n,cmp);con[0]=0;con[1]=1;cn=1;for(i=2; i<n; i++){while(cn>0 && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)cn--;con[++cn]=i;}int tmp=cn;for(i=n-2; i>=0; i--){while(cn>tmp && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)cn--;con[++cn]=i;}
}
double Solve()
{int t,r,l;double ans=999999999;t=r=1;if(cn<3)return 0;for(int i=0; i<cn; i++){while(Sig( Xmult(p[con[i]],p[con[i+1]],p[con[t+1]])-Xmult(p[con[i]],p[con[i+1]],p[con[t]])   )>0)t=(t+1)%cn;while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[r+1]])-Dmult(p[con[i]],p[con[i+1]],p[con[r]])   )>0)r=(r+1)%cn;if(!i) l=r;while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[l+1]])-Dmult(p[con[i]],p[con[i+1]],p[con[l]])   )<=0)l=(l+1)%cn;double d=Dis(p[con[i]],p[con[i+1]]);double tmp=Xmult(p[con[i]],p[con[i+1]],p[con[t]])*( Dmult(p[con[i]],p[con[i+1]],p[con[r]])-Dmult(p[con[i]],p[con[i+1]],p[con[l]]) )/d/d;ans=min(ans,tmp);}return ans;
}
int main()
{int i; int T, cas = 1;scanf("%d", &T);while(T --){scanf("%d",&n);n *= 4;for(i=0; i<n; i++)scanf("%lf%lf",&p[i].x,&p[i].y);Graham();printf("Case #%d:\n%.0f\n",cas ++, Solve());}return 0;
}