poj3608 Bridge Across Islands

发表于 | 更新于

Link

Solution

旋转卡壳

Tips

注意判断的条件和卡的时候的逻辑。 按照DavidLee的这种写法必须要正卡再反卡。

Code

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
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10000+10;
typedef double ld;
const ld eps=1e-7,INF=1e100;
using std::unique;
using std::sort;
using std::swap;
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> T sqr(T x){return x*x;}
template <class T> T abs(T x){return x>0?x:-x;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
	vec operator -(){return vec(-x,-y);}
	ld norm(){return sqrt(x*x+y*y);}
	bool operator <(vec a)
	{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
	void operator +=(vec a){x+=a.x,y+=a.y;}
	void operator -=(vec a){x-=a.x,y-=a.y;}
	bool operator ==(vec a){return x==a.x && y==a.y;}
};
typedef vec point;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
struct line
{
	point a;vec v;
	line(point _a,vec _v):a(_a),v(_v){}
};
ld dist(point a,line l)
{
	vec AB=l.a-a,AC=l.a+l.v-a,BC=l.v;
	point A=a,B=l.a,C=l.a+l.v;
	if(fcmp(inner(BC,-AB))<0) return dist(A,B);
	else if(fcmp(inner(-AC,-BC))<0) return dist(A,C);
	else return abs(outer(AB,BC))/BC.norm();
}
ld caliper(point *p1,int n1,point *p2,int n2)
{
	int c1=1,c2=1;
	for(int i=1;i<=n1;i++) if(p1[i].y<p1[c1].y) c1=i;
	for(int i=1;i<=n2;i++) if(p2[i].y<p2[c2].y) c2=i;
	#define suc(x,n) (x+1>n?1:x+1)
	ld res=INF;
	for(int loop=1;loop<=n1;loop++,c1=suc(c1,n1))
	{
		while(fcmp(outer(p1[suc(c1,n1)]-p1[c1],p2[suc(c2,n2)]-p2[c2]))>0)
			c2=suc(c2,n2);
		line now=line(p1[c1],p1[suc(c1,n1)]-p1[c1]);
		chkmn(res,dist(p2[c2],now));
		chkmn(res,dist(p2[suc(c2,n2)],now));
	}
	#undef suc
	return res;
}
bool cmp(vec a,vec b)
{
	if(outer(a,b)!=0)
		return outer(a,b)>0;
	return inner(a,a)<inner(b,b);
}
void Graham(point *p,int n)
{
	static point stack[MAXN];int top=0;
	int mi=1;
	for(int i=1;i<=n;i++)
		if(p[i]<p[mi]) mi=i;
	p[0]=p[mi];swap(p[mi],p[1]);
	for(int i=1;i<=n;i++) p[i]-=p[0];
	sort(p+2,p+1+n,cmp);
	n=unique(p+1,p+1+n)-p-1;
	for(int i=1;i<=n;i++) p[i]+=p[0];
	p[n+1]=p[1];
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && fcmp(outer(p[i]-stack[i],stack[i]-stack[i-1]))>=0) top--;
		stack[++top]=p[i];
	}
	n=top-1;
	for(int i=1;i<=n;i++) p[i]=stack[i];
}
void WORK(int n1,int n2)
{
	static point p1[MAXN],p2[MAXN];
	for(int i=1;i<=n1;i++) fred(p1[i].x),fred(p1[i].y);
	for(int i=1;i<=n2;i++) fred(p2[i].x),fred(p2[i].y);
	Graham(p1,n1);
	Graham(p2,n2);
	ld ANS=INF;
	chkmn(ANS,caliper(p1,n1,p2,n2));
	chkmn(ANS,caliper(p2,n2,p1,n1));
	printf("%.5lf\n",ANS);
}
int main()
{
	freopen("input","r",stdin);
	int n1,n2;
	while(red(n1),red(n2),n1 && n2)
		WORK(n1,n2);
	return 0;
}