题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1114
题意:求多边形最小外接矩形。
思路:模板。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
struct point
{
double x,y;
point(){}
point(double _x,double _y)
{
x=_x;
y=_y;
}
void get()
{
scanf("%lf%lf",&x,&y);
}
};
const double EPS=1e-8;
const int MAX=1005;
point p[MAX],q[MAX],temp;
int n,m;
int DB(double x)
{
if(x>EPS) return 1;
if(x<-EPS) return -1;
return 0;
}
double Dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//判断p在向量ab的哪一侧
//右侧:返回正值
//左侧:返回负值
//在向量ab上返回0
double cross(point a,point b,point p)
{
return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);
}
int cmp(point a,point b)
{
double x=Dis(a,temp),y=Dis(b,temp);
int flag=DB(cross(temp,a,b));
if(flag) return flag==1;
return DB(x-y)<=0;
}
void Graham(point p[],int n,point q[],int &m)
{
point t;
int i,k=0,a,b;
for(i=1;i<n;i++)
{
a=DB(p[i].y-p[k].y);
b=DB(p[i].x-p[k].x);
if(a==-1||!a&&b==-1) k=i;
}
if(k!=0) t=p[0],p[0]=p[k],p[k]=t;
temp=p[0];
sort(p+1,p+n,cmp);
q[0]=p[0];
q[1]=p[1];
p[n]=p[0];
m=2;
for(i=2;i<=n;i++)
{
while(m>1&&DB(cross(q[m-2],q[m-1],p[i]))<=0) m--;
q[m++]=p[i];
}
m--;
}
//向量点乘
//ab*ac
double dot(point a,point b,point c)
{
return (c.x-a.x)*(b.x-a.x)+(c.y-a.y)*(b.y-a.y);
}
double calMinRect(point pt[],int n)
{
if(n<3) return 0;
int i,p=1,q=1,r;
double ans=1e10,a,b,c;
for(i=0;i<n;i++)
{
while(1)
{
a=cross(pt[i],pt[i+1],pt[p+1]);
b=cross(pt[i],pt[i+1],pt[p]);
if(DB(a-b)<=0) break;
p=(p+1)%n;
}
while(1)
{
a=dot(pt[i],pt[i+1],pt[q+1]);
b=dot(pt[i],pt[i+1],pt[q]);
if(DB(a-b)<=0) break;
q=(q+1)%n;
}
if(!i)r=q;
while(1)
{
a=dot(pt[i],pt[i+1],pt[r+1]);
b=dot(pt[i],pt[i+1],pt[r]);
if(DB(a-b)>0) break;
r=(r+1)%n;
}
a=cross(pt[i],pt[i+1],pt[p]);
b=dot(pt[i],pt[i+1],pt[q])-dot(pt[i],pt[i+1],pt[r]);
c=dot(pt[i],pt[i+1],pt[i+1]);
ans=min(ans,a*b/c);
}
return ans;
}
int main()
{
while(scanf("%d",&n),n)
{
int i;
for(i=0;i<n;i++) p[i].get();
Graham(p,n,q,m);
double ans=calMinRect(q,m);
printf("%.4lf\n",ans);
}
return 0;
}