Rockdu's Blog

Description

Thousands of thousands years ago there was a small kingdom located in the middle of the Pacific Ocean. The territory of the kingdom consists two separated islands. Due to the impact of the ocean current, the shapes of both the islands became convex polygons. The king of the kingdom wanted to establish a bridge to connect the two islands. To minimize the cost, the king asked you, the bishop, to find the minimal distance between the boundaries of the two islands.

Input

Output

Sample Input

4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0

Sample Output

1.00000

Source

做一遍凸包，变成求两个凸包的距离，也就是最短的两端在凸包上的线段的长度。

不难发现，答案要么是两点间的距离，要么是点作垂线垂足在线段上垂线的长度。因为凸包斜率满足单调性，我们可以使用旋转卡壳。

我们改一改原来的算法，在两个凸包上各卡一条直线，一个凸包初始在最高点，一个凸包初始在最低点。然后两条直线都顺时针沿着凸包旋转，哪个斜率大转哪个。每一次统计首先要计算两点距离，其次如果垂足在线段上我们计算垂线长度。判垂足在不在线段上等价于判断点和线段构成的角中有没有钝角，点积一下即可。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, AHigh, BLow;

namespace G2D {
	typedef double T;
	const T eps = 1e-17;
	inline int sgn(T x) {return (x > -eps) - (x < eps);}
	struct P{T x, y;P(){}P(T _x, T _y):x(_x),y(_y){}
			void prt() {cerr << x << " " << y << endl;}
			double calc(){return atan2(x, y);}};
	inline P operator + (const P &A, const P &B) 
		{return P(A.x + B.x, A.y + B.y);}
	inline P operator - (const P &A, const P &B)
		{return P(A.x - B.x, A.y - B.y);}
	inline T operator * (const P &A, const P &B) 
		{return A.x * B.y - B.x * A.y;}
	inline P operator * (const P &A, const T &B)
		{return P(A.x * B, A.y * B);}
	inline T Dot(const P &A, const P &B) 
		{return A.x * B.x + A.y * B.y;}	
	struct Line {
		P s, t; Line(){}
		Line(P _s, P _t):s(_s),t(_t){}
	}; 
	//-1:L  0:M  1:R
	inline int ASide(const P &A, const P &B) {return sgn(A * B);}
	inline int ASide(const P &A, const Line &B) 
		{return sgn((A - B.s) * (B.t - B.s));}
	inline P Itsec(const Line &A, const Line &B) {
		double s1 = (B.s - A.s) * (A.t - A.s);
		double s2 = (A.t - A.s) * (B.t - A.s);
		return (B.t - B.s) * (s1 / (s1 + s2)) + B.s;
	}
	#define sqr(x) ((x) * (x))
	inline T Dis(const P &A, const P &B) 
		{return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));}
	inline T Dis(const Line &A, const P &B) 
		{return abs((B - A.s) * (A.t - A.s)) / Dis(A.s, A.t);}
	P tmp[maxn];
	bool cmp(const P &A, const P &B) {
		return A.x == B.x ? A.y < B.y : A.x < B.x;
	}
	int Convex(P * A, int n) {
		int cnt = 0;
		memcpy(tmp, A, sizeof(P) * (n + 3));
		sort(tmp + 1, tmp + n + 1, cmp);
		A[++cnt] = tmp[1], A[++cnt] = tmp[2];
		for(register int i = 3; i <= n; ++i) {
			while(cnt > 1 && ASide(tmp[i], Line(A[cnt - 1], A[cnt])) < 0) --cnt;
			A[++cnt] = tmp[i];
		}
		for(register int i = n - 1; i >= 1; --i) {
			while(cnt > 1 && ASide(tmp[i], Line(A[cnt - 1], A[cnt])) < 0) --cnt;
			A[++cnt] = tmp[i];
		}
		return cnt - 1;
	}
}

G2D::T x, y;
G2D::P A[maxn], B[maxn], src;
inline int nxt(int x, int n) {return x == n ? 1 : x + 1;}
inline int lst(int x, int n) {return x == 1 ? n : x - 1;}
G2D::T Rev() {
	using namespace G2D;
	T ans = 1e300;
	int at = AHigh, bt = BLow, as, bs, side;
	as = lst(at, n), bs = lst(bt, m);
	Line NA(A[as], A[at]);
	Line NB(B[bt], B[bs]);
	do {
		side = ASide(A[nxt(at, n)] - A[at], B[bt] - B[nxt(bt, m)]);
		if(side < 0) {
			as = at, at = nxt(at, n);
			NA = Line(A[as], A[at]);
			if(Dot(B[bt] - NA.s, NA.t - NA.s) >= 0 &&
				Dot(B[bt] - NA.t, NA.s - NA.t) >= 0)
				ans = min(ans, Dis(NA, B[bt]));
			ans = min(ans, Dis(B[bt], A[as]));
			ans = min(ans, Dis(B[bt], A[at]));
		}
		else {
			bs = bt, bt = nxt(bt, m);
			NB = Line(B[bt], B[bs]);
			if(Dot(A[at] - NB.s, NB.t - NB.s) >= 0 && 
				Dot(A[at] - NB.t, NB.s - NB.t) >= 0)
				ans = min(ans, Dis(NB, A[at]));
			ans = min(ans, Dis(A[at], B[bs]));
			ans = min(ans, Dis(A[at], B[bt]));
		}
	} while(at != AHigh || bt != BLow);
	return ans;
}

int main() {
	//freopen("out.txt", "r", stdin);
	//freopen("ans.txt", "w", stdout);
	while(1) {
		scanf("%d%d", &n, &m);
		if(n + m == 0) break;
		AHigh = BLow = 0;
		A[0].y = -1e300;
		B[0].y = 1e300;
		for(register int i = 1; i <= n; ++i) {
			scanf("%lf%lf", &x, &y);
			A[i] = G2D::P(x, y);
		}
		n = G2D::Convex(A, n);
		for(register int i = 1; i <= n; ++i) {
			if(A[i].y > A[AHigh].y) AHigh = i;
			if(A[i].y == A[AHigh].y && A[i].x > A[AHigh].x) AHigh = i;
		}
		for(register int i = 1; i <= m; ++i) {
			scanf("%lf%lf", &x, &y);
			B[i] = G2D::P(x, y);
		}
		m = G2D::Convex(B, m);
		for(register int i = 1; i <= m; ++i) {
			if(B[i].y < B[BLow].y) BLow = i;
			if(B[i].y == B[BLow].y && B[i].x < B[BLow].x) BLow = i;
		}
		printf("%.5lf\n", Rev());
	}
	return 0;
}