Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

6 1.0 3.00000

1 4.00000

2.0000 1

3 0.0000

3.00000 6

6.0 3.0

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;
}