学步园

题目链接：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;

	void get ()
	{
		scanf("%lf%lf",&x,&y);
    }
}pt[1005],ch[1005];

int n,len;

int DB (double d)
{
	if (fabs(d)<1e-8)
		return 0;
	return d>0?1:-1;
}

double cross (Point p,Point ch,Point x)
{
	return (p.x-x.x)*(ch.y-x.y)-(ch.x-x.x)*(p.y-x.y);
}

int cmp (const void *a,const void *b)
{
	Point aa=*(Point *)a;
	Point bb=*(Point *)b;
	int y=DB(aa.y-bb.y);
	int x=DB(aa.x-bb.x);

	if (y == 0)
		return x==1?1:-1;
	return y;
}

void Graham (Point pt[],Point ch[],int &len,int n)
{
	int i,top=1;
	qsort(pt,n,sizeof(pt[0]),cmp);
    ch[0]=pt[0];
    ch[1]=pt[1];
    for (i=2;i<n;i++)
    {
        while (top>0 && DB(cross(ch[top],pt[i],ch[top-1])) <= 0)
            top--;
        ch[++top]=pt[i];
    }
    int temp=top;
    for (i=n-2;i>=0;i--)
    {
        while (top>temp && DB(cross(ch[top],pt[i],ch[top-1])) <= 0)
            top--;
        ch[++top]=pt[i];
    }
    len=top;
}

double dot(Point a,Point b,Point c)   //求ac在ab边的摄影
{
    return (c.x-a.x)*(b.x-a.x)+(c.y-a.y)*(b.y-a.y);
}

double CalMinRect (Point ch[],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 (DB(cross(ch[i+1],ch[p+1],ch[i])-cross(ch[i+1],ch[p],ch[i])) == 1)
            p=(p+1)%n;
        while (DB(dot(ch[i],ch[i+1],ch[q+1])-dot(ch[i],ch[i+1],ch[q])) == 1)
            q=(q+1)%n;
        if (i == 0)
			r=q;
        while(DB(dot(ch[i],ch[i+1],ch[r+1])-dot(ch[i],ch[i+1],ch[r])) <= 0)
            r=(r+1)%n;

        a=cross(ch[i],ch[i+1],ch[p]);
        b=dot(ch[i],ch[i+1],ch[q])-dot(ch[i],ch[i+1],ch[r]);
        c=dot(ch[i],ch[i+1],ch[i+1]);
        ans=min(ans,a*b/c);
    }
    return ans;
}

int main ()
{
	while (scanf("%d",&n) && n!=0)
	{
		for (int i=0;i<n;i++)
			pt[i].get();
		if (n<3)
		{
			printf("0.0000\n");
			continue;
		}
		Graham (pt,ch,len,n);
		printf("%.4lf\n",CalMinRect (ch,len));
	}
	return 0;
}