●BZOJ 1185 [HNOI2007]最小矩形覆盖

时间：2021-10-20 05:31:54

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=1185

题解：

计算几何，凸包，旋转卡壳

结论：矩形的某一条边在凸包的一条边所在的直线上。

（证不来，网上好像也没看到证明。。。诶。。。）

通过结论，问题转化为枚举凸包每条边，然后求出当矩形的一条边在该边所在的直线上时的最小矩形。

即我们需要求出在凸包上，相对与这条边的最右边，最上面和最左边的点，

而最上面的点可以通过叉积得到最优位置，

最左和最右就可以通过点积的到最优位置，（一个点积最大，一个点积最小）。

同时由于随着边的顺时针枚举，这三个东西都具有单调性，所以用旋转卡壳。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50050

using namespace std;

const double eps=1e-10;

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

};

typedef Point Vector;

bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double k){return Vector(A.x*k,A.y*k);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

Point D[MAXN],C[MAXN],ANS[6],tmp[6];

int Andrew(int dnt){

	int cnt=0,k;

	sort(D+1,D+dnt+1);

	for(int i=1;i<=dnt;i++){

		while(cnt>1&&sign((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;

		C[++cnt]=D[i];

	} k=cnt;

	for(int i=dnt-1;i>=1;i--){

		while(cnt>k&&sign((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;

		C[++cnt]=D[i];

	}

	return cnt-(dnt>1);

}

double TA(Point P1,Point P2,Point P){//Triangle_Area

	return fabs((P-P1)^(P-P2))/2;

}

double PP(Point P1,Point P2,Point P){//Projection_Product

	return (P-P1)*(P2-P1);

}

double GL(Vector A){//Get_Length

	return sqrt(A*A);

}

Vector UV(Vector A){//Unit_Vector

	double len=GL(A);

	return Vector(A.x*(1/len),A.y*(1/len));

}

double DTL(Point P,Point P1,Point P2){//Distant_to_Line

	return fabs(((P-P1)^(P-P2))/GL(P2-P1));

}

double rectangle(Vector v,Point d,Point r,Point u,Point l){

	static Vector _v,w; static double t,h;

	_v=Vector(-v.y,v.x);

	v=UV(v); _v=UV(_v); w=l-d;

	t=(w^_v)/(v^_v);

	tmp[1]=d+(v*t);

	h=DTL(r,tmp[1],tmp[1]+_v);

	tmp[2]=tmp[1]+v*h;

	h=DTL(u,tmp[1],tmp[1]+v);

	tmp[4]=tmp[1]+_v*h;

	tmp[3]=tmp[1]+((tmp[2]-tmp[1])+(tmp[4]-tmp[1]));

	return TA(tmp[1],tmp[3],tmp[4])+TA(tmp[1],tmp[3],tmp[2]);

}

double RC(int cnt){//Rotating_Calipers

	double S=1e300,_S; C[cnt+1]=C[1];

	int l,r=1,u=1;

	for(int i=1;i<=cnt;i++){

		while(sign(PP(C[i],C[i+1],C[r])-PP(C[i],C[i+1],C[r+1]))<=0) r=r%cnt+1;

		while(sign(TA(C[i],C[i+1],C[u])-TA(C[i],C[i+1],C[u+1]))<=0) u=u%cnt+1;

		if(i==1) l=r;

		while(sign(PP(C[i],C[i+1],C[l])-PP(C[i],C[i+1],C[l+1]))>0) l=l%cnt+1;

		_S=rectangle(C[i+1]-C[i],C[i],C[r],C[u],C[l]);

		if(sign(S-_S)>0){

			S=_S;for(int k=1;k<=4;k++) ANS[k]=tmp[k];

		}

	}

	return S;

}

void printPoint(){

	int p=1; for(int i=2;i<=4;i++)

		if(sign(ANS[i].y-ANS[p].y)<0||(sign(ANS[i].y-ANS[p].y==0)&&sign(ANS[i].x-ANS[p].x)<0)) p=i;

	for(int i=1;i<=4;i++,p=p%4+1) printf("%lf %lf\n",ANS[p].x,ANS[p].y);

}

int main(){

	int n; scanf("%d",&n);

	for(int i=1;i<=n;i++) D[i].Read();

	printf("%.5lf\n",RC(Andrew(n)));

	printPoint();

	return 0;

}

　　

相关文章