Bzoj1185 [hnoi2007]最小矩形覆盖

细节超多的计几题

Posted by yjjr's blog on February 10, 2018

标签:计算几何-旋转卡壳

题目

题目传送门

题目描述

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

第一行为一个整数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

分析

题意大概是给出一些点的坐标,求覆盖这组点的最小矩形,并输出矩形四点坐标

结论:矩形的一条边一定在这些点的凸包上

枚举凸包上的边,然后用旋转卡壳找另外三个点

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-9
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=5e4+6;
double ans=1e60;int n,top,k=0;
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[maxn],s[maxn],a[6];
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;else return t>0;
}
void graham(){
	rep(i,2,n)if(p[i]<p[1])swap(p[i],p[1]);
	sort(p+2,p+n+1,cmp);
	s[++top]=p[1];
	rep(i,2,n){
		while(top>1&&((s[top]-s[top-1])*(p[i]-s[top]))<eps)top--;
		s[++top]=p[i];
	}
	s[0]=s[top];
}
void RC(){
	int l=1,r=1,p=1;double L,R,D,H;
	rep(i,0,top-1){
		D=dis(s[i]-s[i+1]);
		while((s[i+1]-s[i])*(s[p+1]-s[i])-(s[i+1]-s[i])*(s[p]-s[i])>-eps)p=(p+1)%top;
		while((s[i+1]-s[i])/(s[r+1]-s[i])-(s[i+1]-s[i])/(s[r]-s[i])>-eps)r=(r+1)%top;
		if(i==0)l=r;
		while((s[i+1]-s[i])/(s[l+1]-s[i])-(s[i+1]-s[i])/(s[l]-s[i])<eps)l=(l+1)%top;
		L=(s[i+1]-s[i])/(s[l]-s[i])/D,R=(s[i+1]-s[i])/(s[r]-s[i])/D;
		H=(s[i+1]-s[i])*(s[p]-s[i])/D;
		if(H<0)H=-H;
		double tmp=(R-L)*H;
		if(tmp<ans){
			ans=tmp;
			a[0]=s[i]+(s[i+1]-s[i])*(R/D);
			a[1]=a[0]+(s[r]-a[0])*(H/dis(a[0]-s[r]));
			a[2]=a[1]-(a[0]-s[i])*((R-L)/dis(s[i]-a[0]));
			a[3]=a[2]-(a[1]-a[0]);
		}
	}
}
int main()
{
	n=read();
	rep(i,1,n)scanf("%lf%lf",&p[i].x,&p[i].y);
	graham();RC();
	printf("%.5lf\n",ans);
	rep(i,1,3)
		if(a[i]<a[k])k=i;
	rep(i,0,3)printf("%.5lf %.5lf\n",a[(i+k)%4].x,a[(i+k)%4].y);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr