「BZOJ1185」[HNOI2007] 最小矩形覆盖

2014年12月24日8,3167

Description

题解

首先有一个结论，矩形的一条边一定在凸包上！！！

枚举凸包上的边

用旋转卡壳在凸包上找矩形另外三点。。。

注意精度问题

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define eps 1e-8
#define inf 1000000000
using namespace std;
double ans=1e60;
int n,top;
struct P{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(P a,P b){
		return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;
	}
	friend bool operator==(P a,P b){
		return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
	}
	friend bool operator!=(P a,P b){
		return !(a==b);
	}
	friend P operator+(P a,P b){
		return P(a.x+b.x,a.y+b.y);
	}
	friend P operator-(P a,P b){
		return P(a.x-b.x,a.y-b.y);
	}
	friend double operator*(P a,P b){
		return a.x*b.y-a.y*b.x;
	}
	friend P operator*(P a,double b){
		return P(a.x*b,a.y*b);
	}
	friend double operator/(P a,P b){
		return a.x*b.x+a.y*b.y;
	}
	friend double dis(P a){
		return sqrt(a.x*a.x+a.y*a.y);
	}
}p[50005],q[50005],t[5];
bool cmp(P a,P b)
{
	double t=(a-p[1])*(b-p[1]);
	if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;
	return t>0;
}
void graham()
{
	for(int i=2;i<=n;i++)
		if(p[i]<p[1])
			swap(p[i],p[1]);
	sort(p+2,p+n+1,cmp);
	q[++top]=p[1];
	for(int i=2;i<=n;i++)
	{
		while(top>1&&(q[top]-q[top-1])*(p[i]-q[top])<eps)top--;
		q[++top]=p[i];
	}
	q[0]=q[top];
}
void RC()
{
	int l=1,r=1,p=1;
	double L,R,D,H;
	for(int i=0;i<top;i++)
	{
		D=dis(q[i]-q[i+1]);
		while((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps)p=(p+1)%top;
		while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top;
		if(i==0)l=r;
		while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps)l=(l+1)%top;
	    L=(q[i+1]-q[i])/(q[l]-q[i])/D,R=(q[i+1]-q[i])/(q[r]-q[i])/D;
		H=(q[i+1]-q[i])*(q[p]-q[i])/D;
		if(H<0)H=-H;
		double tmp=(R-L)*H;
		if(tmp<ans)
		{
		    ans=tmp;
			t[0]=q[i]+(q[i+1]-q[i])*(R/D);
			t[1]=t[0]+(q[r]-t[0])*(H/dis(t[0]-q[r]));
			t[2]=t[1]-(t[0]-q[i])*((R-L)/dis(q[i]-t[0]));
			t[3]=t[2]-(t[1]-t[0]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	graham();
	RC();
	printf("%.5lf\n",ans);
	int fir=0;
	for(int i=1;i<=3;i++)
		if(t[i]<t[fir])
			fir=i;
	for(int i=0;i<=3;i++)
		printf("%.5lf %.5lf\n",t[(i+fir)%4].x,t[(i+fir)%4].y);
	return 0;
}

100

101

102

103

104

105

106

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<set>

#define eps 1e-8

#define inf 1000000000

using namespace std;

double ans=1e60;

int n,top;

struct P{

double x,y;

P(){}

P(double _x,double _y):x(_x),y(_y){}

friend bool operator<(P a,P b){

return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;

}

friend bool operator==(P a,P b){

return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;

}

friend bool operator!=(P a,P b){

return !(a==b);

}

friend P operator+(P a,P b){

return P(a.x+b.x,a.y+b.y);

}

friend P operator-(P a,P b){

return P(a.x-b.x,a.y-b.y);

}

friend double operator*(P a,P b){

return a.x*b.y-a.y*b.x;

}

friend P operator*(P a,double b){

return P(a.x*b,a.y*b);

}

friend double operator/(P a,P b){

return a.x*b.x+a.y*b.y;

}

friend double dis(P a){

return sqrt(a.x*a.x+a.y*a.y);

}

}p[50005],q[50005],t[5];

bool cmp(P a,P b)

{

double t=(a-p[1])*(b-p[1]);

if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;

return t>0;

}

void graham()

{

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

if(p[i]<p[1])

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

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

q[++top]=p[1];

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

{

while(top>1&&(q[top]-q[top-1])*(p[i]-q[top])<eps)top--;

q[++top]=p[i];

}

q[0]=q[top];

}

void RC()

{

int l=1,r=1,p=1;

double L,R,D,H;

for(int i=0;i<top;i++)

{

D=dis(q[i]-q[i+1]);

while((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps)p=(p+1)%top;

while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top;

if(i==0)l=r;

while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps)l=(l+1)%top;

L=(q[i+1]-q[i])/(q[l]-q[i])/D,R=(q[i+1]-q[i])/(q[r]-q[i])/D;

H=(q[i+1]-q[i])*(q[p]-q[i])/D;

if(H<0)H=-H;

double tmp=(R-L)*H;

if(tmp<ans)

{

ans=tmp;

t[0]=q[i]+(q[i+1]-q[i])*(R/D);

t[1]=t[0]+(q[r]-t[0])*(H/dis(t[0]-q[r]));

t[2]=t[1]-(t[0]-q[i])*((R-L)/dis(q[i]-t[0]));

t[3]=t[2]-(t[1]-t[0]);

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%lf%lf",&p[i].x,&p[i].y);

graham();

RC();

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

int fir=0;

for(int i=1;i<=3;i++)

if(t[i]<t[fir])

fir=i;

for(int i=0;i<=3;i++)

printf("%.5lf %.5lf\n",t[(i+fir)%4].x,t[(i+fir)%4].y);

return 0;

}

« 「BZOJ2300」[HAOI2011] 防线修建「POJ2187」Beauty Contest »

罗崚骁

敢问有一条边必在凸包上这个结论如何证明……

hzwer

思考了一下，我只会证明三角形

罗崚骁

能证三角形的话……试一下归纳法？QWQ

BPM136

其实大概脑补了下证明是这样的，因为我们首先可以很轻易的想到必然有一个点在矩形上否则必然不是最优解，然后因为如果只有一点在矩形上，那我们可以收缩这个矩形至凸包上两个点都在矩形上，这时候有两种情况，一种是对角线，一种是相邻的两个点（于是就不加以讨论），因为这是一个矩形，所以对角线一定比边要长，所以当对角线在矩形上时，我们假设这个矩形的一边长度已经固定（实际上这个长度就是我们卡左右两点的长度），因为这是一个凸包，所以旋转时不可能有除了当前枚举点左右相邻点之外的点落在矩形上，否则左右相邻点必然不在这个矩形内，然而旋转的时候高（也就是到对称点的距离）的长度是一个单峰函数，它在相邻两点都在矩形上时取到最小值（凸包的对顶点性质），而这两点吧必然构成这个矩形一边否则我们可以旋转使它其中两个点落在矩形上，然后相同思考方法即可，主要就是要去掉我们卡左右点时的影响，证明的时候把这个矩形的底长看成是固定的然后再证就简单多了

BPM136

只是只弱菜错了求轻喷别太重QAQ

张凯羿

高亮没了

张凯羿

哦……是我的网速太渣了 = = 、

hzwer.com _ Home | http://hzwer.com

「BZOJ1185」[HNOI2007] 最小矩形覆盖

Description

题解

分类目录

热门文章

Myfriends

近期评论