洛谷P3187 [HNOI2007]最小矩形覆盖
? 解题记录 ? ? 洛谷 ? ? 旋转卡壳 ? ? 凸包 ?    2018-02-28 10:10:02    628    0    0

题目描述

给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,输出所求矩形的面积和四个顶点坐标

输入输出格式

输入格式:

 

第一行为一个整数n(3<=n<=50000),从第2至第n+1行每行有两个浮点数,表示一个顶点的x和y坐标,不用科学计数法

 

输出格式:

 

第一行为一个浮点数,表示所求矩形的面积(精确到小数点后5位),接下来4行每行表示一个顶点坐标,要求第一行为y坐标最小的顶点,其后按逆时针输出顶点坐标.如果用相同y坐标,先输出最小x坐标的顶点

 

输入输出样例

输入样例#1: 复制
6 1.0 3.00000

1 4.00000

2.0000 1

3 0.0000

3.00000 6

6.0 3.0
输出样例#1: 复制
18.00000

3.00000 0.00000

6.00000 3.00000

3.00000 6.00000

0.00000 3.00000

说明

感谢 @intruder 提供题目简述

这道题想着简单,写着有毒。我们先做一个凸包,然后旋转卡壳。这个旋转卡壳需要卡3个点:以当前直线为下边的上左右边界,每一次旋转我们同时处理移动三个点就行了。这样我们带一个大常数就可以卡出所有可能最优的矩形。关于旋转卡壳可以看这一篇博客:我不是“这篇博客”o(>﹏<)o

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=11;
LL dp[2][1<<(maxn+1)];
int n,m,i,j,now,news;//n行m列  

bool getbit(int num,int k){  //从第0开始 
	return num&(1<<k);
}

void editbit(int & num,int k,bool val){
	int ret;
	ret=num-(getbit(num,k)<<k)+(val<<k);
	num=ret;
}

int rt(int num){
	return (num>>=1);
}

int main(){
	while(1){
		memset(dp,0,sizeof(dp));
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)	break;
		if(n>m) swap(n,m);
		int ini=(1<<n)-1;editbit(ini,n-1,0);
		dp[0][ini]=1, now = 0;
		for(register int i=0;i<m;i++)
			for(register int j=0;j<n;j++){
				if(i==0 && j==0) continue;
				now ^= 1;
				memset(dp[now], 0, sizeof(dp[now]));
				for(register int k=0;k<1<<n;k++){
					if(getbit(k,0)==0)
						news=k>>1,editbit(news,n-1,1),dp[now][news]+=dp[now ^ 1][k];
					if((getbit(k,0)==1 || i==0) && (getbit(k,n-1)==0 && j!=0))
						news=k>>1,editbit(news,n-2,1),editbit(news,n-1,1),dp[now][news]+=dp[now ^ 1][k];
					if(getbit(k,0)==1 || i==0)
						news=k>>1,dp[now][news]+=dp[now ^ 1][k];						
				}
			} 
		printf("%lld\n",dp[now][(1<<n)-1]);
	}
	return 0;
}

 

上一篇: 洛谷P4196 [CQOI2006]凸多边形

下一篇: POJ2411 Mondriaan's Dream

628 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航