学步园

Problem F

Smallest Bounding Rectangle

Input: standard input

Output: standard output

Time Limit: 3 seconds

Given the Cartesian coordinates of n (> 0) 2-dimensional points, write a program that computes the area of their smallest bounding rectangle (smallest rectangle containing all the given points).

Input

The input file may contain multiple test cases. Each test case begins with a line containing a positive integern (< 1001) indicating the number of points in this test case. Then followsn lines each containing two real numbers giving respectively
the x- andy-coordinates of a point. The input terminates with a test case containing a value 0 forn
which must not be processed.  

Output

For each test case in the input print a line containing the area of the smallest bounding rectangle rounded to the 4th digit after the decimal point.

Sample Input

3
-3.000 5.000
7.000 9.000
17.000 5.000
4
10.000 10.000
10.000 20.000
20.000 20.000
20.000 10.000
0

Sample Output

80.0000
100.0000

“The art of mathematics, as of life, is knowing which truths are useless.”

我的解题思路：我是猜的，最小的矩形一定经过所有点围成的凸包的一条边，因此枚举凸包的边即可。效率 O(n^2)

虽然无法证明，但是AC了，说明我的想法是比较正确的。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn=1010;
const double eps=1e-9;
const double pi=acos(double(-1));

struct point{
	double x,y;
	point(double x0=0,double y0=0):x(x0),y(y0){}
	friend bool operator < (point a,point b){
		if(a.y!=b.y) return a.y<b.y;
		else return a.x<b.x;
	}
	double getdis(point q){
		return sqrt( (x-q.x)*(x-q.x)+(y-q.y)*(y-q.y) );
	}
}p[maxn];

struct line{//Line ax+by+c=0
	double a,b,c;
	line(double a0=0,double b0=0,double c0=0){
		a=a0;
		b=b0;
		c=c0;
	}
	double getpdis(point q){
		return abs(a*q.x+b*q.y+c)/sqrt(a*a+b*b);
	}
};

int n,top;

double xchen(point a,point b,point c){
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double dchen(point a,point b,point c){
	return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);
}

bool cmp(point a,point b){
	if(fabs(xchen(p[0],a,b))<eps) return a.getdis(p[0])<b.getdis(p[0]);
	else return xchen(p[0],a,b)>0;
}

void deal(){
	top=1;
	sort(p,p+n);
	sort(p+1,p+n,cmp);
	for(int i=2;i<n;i++){
		while(top>0 && xchen(p[top-1],p[top],p[i])<=0) top--;
		p[++top]=p[i];
	}
	p[++top]=p[0];
}


void input(){
	for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
}

line getL(point p1,point p2){//get the line that cross point p1 and p2
	//a=y1-y2,b=x2-x1,c=x1*y2-x2*y1;
	line tmp;
	tmp.a=p1.y-p2.y;
	tmp.b=p2.x-p1.x;
	tmp.c=p1.x*p2.y-p2.x*p1.y;
	//cout<<tmp.a<<" "<<tmp.b<<" "<<tmp.c<<endl;
	return tmp;
}

line getpl(line l,point q){
	line tmp=l;
	tmp.a=-l.b;
	tmp.b=l.a;
	tmp.c=-tmp.a*q.x-tmp.b*q.y;
	return tmp;
}

point getCrossPoint(line l1,line l2){//get the cross point of line l1 and l2 
	point tmp;
	tmp.x=(l1.b*l2.c-l2.b*l1.c)/(l1.a*l2.b-l1.b*l2.a);
	tmp.y=(l1.c*l2.a-l2.c*l1.a)/(l1.a*l2.b-l1.b*l2.a);
	return tmp;
}

void computing(){
	double ans=1e12;
	deal();
	for(int i=0;i<top;i++){
		line l=getL(p[i],p[i+1]);
		point lpoint(1e12,1e12),rpoint(-1e12,-1e12),tmp;
		double maxh=0;
		for(int i=0;i<top;i++){
			double tmpdis=l.getpdis(p[i]);
			if(tmpdis>maxh) maxh=tmpdis;
			tmp=getCrossPoint(l, getpl(l,p[i]) );
			if(tmp.x<lpoint.x-eps) lpoint=tmp;
			if( fabs(tmp.x-lpoint.x)<eps && tmp.y<lpoint.y)   lpoint=tmp;
			if(tmp.x>rpoint.x) rpoint=tmp;
			if( fabs(tmp.x-rpoint.x)<eps && tmp.y>rpoint.y)   rpoint=tmp;
		}
		if( lpoint.getdis(rpoint)*maxh <ans ) ans=lpoint.getdis(rpoint)*maxh;
	}
	printf("%.4lf\n",ans);
}

int main(){
	while(scanf("%d",&n)!=EOF && n>0){
		input();
		computing();
	}
	return 0;
}