判断矩形能包围点集的最小面积：凸包
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define Max 2147483647
#define INF 0x7fffffff
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define repu(i, a, b) for(int i = (a); i < (b); i++)
const double PI=-acos(-1.0);
#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?-: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[],a,b);
if(d>)
return ;
if(d== && Dis(p[],a)<Dis(p[],b))
return ;
return ;
}
double min(double a,double b)
{
return a<b?a:b;
}
void Graham()
{
int i,ind=;
for(i=; 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[]);
sort(p+,p+n,cmp);
con[]=;
con[]=;
cn=;
for(i=; i<n; i++)
{
while(cn> && Sig(Xmult(p[con[cn-]],p[con[cn]],p[i]))<=)
cn--;
con[++cn]=i;
}
int tmp=cn;
for(i=n-; i>=; i--)
{
while(cn>tmp && Sig(Xmult(p[con[cn-]],p[con[cn]],p[i]))<=)
cn--;
con[++cn]=i;
}
}
double Solve()
{
int t,r,l;
double ans=;
t=r=;
if(cn<)
return ;
for(int i=; i<cn; i++)
{
while(Sig( Xmult(p[con[i]],p[con[i+]],p[con[t+]])-
Xmult(p[con[i]],p[con[i+]],p[con[t]]) )>)
t=(t+)%cn;
while(Sig( Dmult(p[con[i]],p[con[i+]],p[con[r+]])-
Dmult(p[con[i]],p[con[i+]],p[con[r]]) )>)
r=(r+)%cn;
if(!i) l=r;
while(Sig( Dmult(p[con[i]],p[con[i+]],p[con[l+]])-
Dmult(p[con[i]],p[con[i+]],p[con[l]]) )<=)
l=(l+)%cn;
double d=Dis(p[con[i]],p[con[i+]]);
double tmp=Xmult(p[con[i]],p[con[i+]],p[con[t]])*
( Dmult(p[con[i]],p[con[i+]],p[con[r]])-
Dmult(p[con[i]],p[con[i+]],p[con[l]]) )/d/d;
ans=min(ans,tmp);
}
return ans;
}
int main()
{
int i,T;
scanf("%d",&T);
repu(kase,,T+)
{
scanf("%d",&n);
n *= ;
for(i=; i<n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
Graham();
printf("Case #%d:\n%.0lf\n",kase,Solve());
}
return ;
}