bzoj 1185 [HNOI2007]最小矩形覆盖凸包+旋转卡壳

题目大意

用最小矩形覆盖平面上所有的点

分析

有一结论：最小矩形中有一条边在凸包的边上，不然可以旋转一个角度让面积变小

简略证明

我们逆时针枚举一条边

用旋转卡壳维护此时最左，最右，最上的点

注意

注意凸包后点数不再是n

吐槽

凸包后点数是n，bzoj上就过了？？？

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef double db;

const db eps=1e-9;

const int M=50007;

int n;

struct pt{

	db x,y;

	pt(db _x=0.0,db _y=0.0){x=_x; y=_y;}

}p[M],s[M]; int tot;

bool eq(db x,db y){return fabs(y-x)<=eps;}

bool le(db x,db y){return eq(x,y)||x<y;}

pt operator -(pt x,pt y){return pt(x.x-y.x,x.y-y.y);}

pt operator +(pt x,pt y){return pt(x.x+y.x,x.y+y.y);}

bool operator <(pt x,pt y){return (x.y!=y.y)?(x.y<y.y):(x.x<y.x);}

bool operator ==(pt x,pt y){return eq(x.x,y.x)&&eq(x.y,y.y);};

pt operator *(pt x,db d){return pt(x.x*d,x.y*d);}

pt operator /(pt x,db d){return pt(x.x/d,x.y/d);}

db dot(pt x,pt y){

	return x.x*y.x+x.y*y.y;

}

db cross(pt x,pt y){

	return x.x*y.y-x.y*y.x;

}

db length(pt x){

	return sqrt(dot(x,x));

}

db area(pt x,pt y,pt z){

	return cross(y-x,z-x);

}

db shadow(pt x,pt y,pt to){

	return dot(y-x,to-x)/length(to-x);

}

pt lf_90(pt x){

	return pt(-x.y,x.x);

}

bool cmp(pt x,pt y){

	db tp=area(p[1],x,y);

	if(eq(tp,0)) return length(x-p[1])<length(y-p[1]);

	return tp>0;

}

void convex(){

	int i,ii=1;

 	for(i=2;i<=n;i++) if(p[i]<p[ii]) ii=i;

 	swap(p[1],p[ii]);

 	sort(p+2,p+n+1,cmp);

 	s[tot=1]=p[1];

 	for(i=2;i<=n;i++){

 		while(tot>1&&le(area(s[tot-1],s[tot],p[i]),0)) tot--;

 		s[++tot]=p[i];

	 }

}

int main(){

	int i,p1,p2,p3;

	db tp1,tp2,tp3,tp4,ans;

	pt a[5],tp;

	scanf("%d",&n);

	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);

	convex();

	s[0]=s[tot];//要算每一条边，加上tot-0的

	ans=1e32;

	p1=1,p2=1,p3=1;

	for(i=0;i<tot;i++){

		if(s[i]==s[i+1]) continue;

		while(le(area(s[i],s[i+1],s[p3]),area(s[i],s[i+1],s[p3%tot+1]))) p3=p3%tot+1;

		if(i==0) p1=p3;//第一次找卡壳特例

		while(le(shadow(s[i],s[p1%tot+1],s[i+1]),shadow(s[i],s[p1],s[i+1]))) p1=p1%tot+1;

		while(le(shadow(s[i+1],s[p2%tot+1],s[i]),shadow(s[i+1],s[p2],s[i]))) p2=p2%tot+1;

		tp1=length(s[i+1]-s[i]);

		tp2=area(s[i],s[i+1],s[p3])/tp1;

		tp3=fabs(shadow(s[i],s[p1],s[i+1]));

		tp4=fabs(shadow(s[i+1],s[p2],s[i]));

		if(le((tp1+tp3+tp4)*tp2,ans)){

			ans=(tp1+tp3+tp4)*tp2;

			tp=s[i+1]-s[i];

			a[1]=s[i]-tp*(tp3/tp1);

			a[2]=s[i+1]+tp*(tp4/tp1);

			tp=lf_90(tp);

			a[3]=a[2]+tp*(tp2/tp1);

			a[4]=a[1]+tp*(tp2/tp1);

		}

	}

	printf("%.5lf\n",ans+eps);

	int ii=1;

	for(i=2;i<=4;i++) if(a[i]<a[ii]) ii=i;

	printf("%.5lf %.5lf\n",a[ii].x+eps,a[ii].y+eps);

	for(i=ii%4+1;i!=ii;i=i%4+1) printf("%.5lf %.5lf\n",a[i].x+eps,a[i].y+eps);

	return 0;

}

巴特西

bzoj 1185 [HNOI2007]最小矩形覆盖凸包+旋转卡壳

题目大意

分析

注意

吐槽

solution

最新文章

热门文章

巴特西

bzoj 1185 [HNOI2007]最小矩形覆盖 凸包+旋转卡壳

题目大意

分析

注意

吐槽

solution

最新文章

热门文章

bzoj 1185 [HNOI2007]最小矩形覆盖凸包+旋转卡壳