旋转卡壳——矩形覆盖

发表于

NKOJ4405 HNOI2007 最小矩形覆盖 传送门

居然是纸质题面，十年前的OI真是jin啊

1185_1

1185_1

Solution

极度卡精题。。。

首先这个最小矩形一定过凸包上的点，且有一条边经过凸包上的一边

那么我们枚举这条边

pic0117

这条边为$\vec {AB}$

利用旋转卡壳（叉积），可得在这条边最上方的点（矩形上界）

利用点积，可得在这条边最左侧和右侧的点（矩形左右界）

设最上方的点为$C$，左侧和右侧的为$D$和$E$

矩形四个角为$F,G,H,I$

利用点积求得$|\vec {AG} |$和$ |\vec {BF} | $，得到底边长

利用叉积求得高$h$，即利用单位面积，$h=\frac {\vec {AB}*\vec {AC}} {|\vec {AB}|}$

就可以算出现在的矩形面积

再用$\vec {AB} * \frac {|\vec {AG}|} {|\vec {AB}|}$ ，求得$\vec G、\vec F$

利用$\vec {AB}$ 的方向向量乘以$h$ ，求得$\vec {GI}$，从而得到$\vec H 、\vec I$

就这样。。注意细节就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef double db;
const db eps=1e-10;
const db pi=acos(-1.0);
const int N=50005;
#define DEB 0

struct Point{
	db x,y;
	void Rotate(db theta){
		db a=x,b=y;
		x=a*cos(theta)-b*sin(theta);
		y=a*sin(theta)+b*cos(theta);
	}
	Point(){}
	Point(db a,db b){
		x=a+eps,y=b+eps;
		this->Rotate(eps);
	}
}A[N],T[N];
bool operator < (const Point& lhs,const Point& rhs) {
	return lhs.x<rhs.x||(lhs.x==rhs.x&&lhs.y<rhs.y);
}
Point operator + (const Point& lhs,const Point& rhs){
	return Point(lhs.x+rhs.x,lhs.y+rhs.y);
}
Point operator - (const Point& lhs,const Point& rhs){
	return Point(lhs.x-rhs.x,lhs.y-rhs.y);
}
db operator * (const Point& lhs,const Point& rhs){
	return lhs.x*rhs.x+lhs.y*rhs.y;
}
Point operator * (const Point& lhs,db lambda){
	return Point(lhs.x*lambda,lhs.y*lambda);
}
Point operator / (const Point& lhs,db lambda){
	return Point(lhs.x/lambda,lhs.y/lambda);
}
db operator ^ (const Point& lhs,const Point& rhs){
	return lhs.x*rhs.y-lhs.y*rhs.x;
}
db mod(const Point& t){
	return sqrt(t.x*t.x+t.y*t.y);
}
int fcmp(db x,db y){/*
	if(x-y<eps)return -1;
	if(x-y>-eps)return 1;
	return 0;*/
	if(fabs(x-y)<eps)return 0;
	if(x-y<-eps)return -1;
	if(x-y>eps)return 1;
}

int n,tot;
void Graham(){
	sort(A+1,A+1+n);
	int i,t;
	for(i=1;i<=n;i++){
		while(tot>1&&fcmp((T[tot]-T[tot-1])^(A[i]-T[tot-1]),0)!=1)tot--;
		T[++tot]=A[i];
	}
	t=tot;
	for(i=n-1;i;i--){
		while(tot>t&&fcmp((T[tot]-T[tot-1])^(A[i]-T[tot-1]),0)!=1)tot--;
		T[++tot]=A[i];
	}
	tot--;
}

int c[5];
Point g[5];
void RC(int x){
	int i;
	c[1]=(x+1)%tot+1;
	while(fcmp((T[x+1]-T[x])^(T[c[1]]-T[x]),(T[x+1]-T[x])^(T[c[1]+1]-T[x]))<0)
		c[1]=c[1]%tot+1;
	c[2]=x%tot+1;
	while(fcmp((T[c[2]]-T[x])*(T[x+1]-T[x]),(T[c[2]+1]-T[x])*(T[x+1]-T[x]))<0)
		c[2]=c[2]%tot+1;
	c[3]=c[1]%tot;
	while(fcmp((T[c[3]]-T[x])*(T[x+1]-T[x]),(T[c[3]+1]-T[x])*(T[x+1]-T[x]))>0)
		c[3]=c[3]%tot+1;
}
int main(){
	int i,j,k;
	db x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%lf%lf",&x,&y);
		A[i]=Point(x,y);
//		A[i].x=x,A[i].y=y;
	}
	Graham();
#if DEB
	RC(5);
	for(i=1;i<=3;i++)
		printf("%.3lf %.3lf\n",T[c[i]].x,T[c[i]].y);
#endif
	db len,h,l1,l2,maxx=1e9;
	Point tmp,ttt;
	for(i=1;i<=tot;i++){
		RC(i);
		len=mod(T[i+1]-T[i]);
		h=((T[i+1]-T[i])^(T[c[1]]-T[i]))/mod(T[i+1]-T[i]);
		l1=(T[c[2]]-T[i])*(T[i+1]-T[i])/len;
		l2=(T[c[3]]-T[i+1])*(T[i]-T[i+1])/len;
		if(fcmp((l1+l2-len)*h,maxx)<0){
			maxx=(l1+l2-len)*h;
			
			tmp=(T[i+1]-T[i])*(l1/len);
			g[1]=T[i]+tmp;
			
			tmp=(T[i]-T[i+1])*(l2/len);
			g[4]=T[i+1]+tmp;
			
			ttt=(T[i+1]-T[i])/mod(T[i+1]-T[i]);
			ttt.Rotate(pi/2);
			tmp=ttt*h;
			g[2]=g[1]+tmp;
			g[3]=g[4]+tmp;
		}
	}
	printf("%.6lf\n",maxx);
	int lb=1;
	for(i=1;i<=4;i++)
		if(fcmp(g[i].y,g[lb].y)<0||(fcmp(g[i].y,g[lb].y)==0&&fcmp(g[i].x,g[lb].x)<0))lb=i;

	for(i=0;i<=3;i++){
		j=(lb+i-1)%4+1;
		if(fcmp(fabs(g[j].x),0.00001)<0)printf("0.00000 ");
		else printf("%.5lf ",g[j].x);
		if(fcmp(fabs(g[j].y),0.00001)<0)printf("0.00000\n");
		else printf("%.5lf\n",g[j].y);
	}
}