【旋转卡壳】POJ 3608 Bridge Across Islands

KIDx的解题报告

 

题目链接：http://poj.org/problem?id=3608

 

题意：求两凸包之间的最小距离。

随便YY的一个旋转卡壳竟然1A水过。。。纪念一下~~~

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define M 50005
#define eps 1e-8

struct point{
	double x, y;
}P;

struct line{
	line (point a, point b) {s=a; e=b;}
	line (){}
	point s, e;
};

double dis (point a, point b, int id = 0)
{
	if (id) return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
	return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double dot (point a, point b, point c)
{
	return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y);
}

double relation (point p, line l)
{ return dot (l.s, p, l.e) / (dis (l.s, l.e)*dis (l.s, l.e)); }

point perpendicular (point p, line l)			//求点C到线段AB所在直线的垂足P
{
	double r = relation (p, l);
	point tp;
	tp.x = l.s.x + r*(l.e.x-l.s.x);
	tp.y = l.s.y + r*(l.e.y-l.s.y);
	return tp;
}

//求点p到线段l的最短距离,并返回线段上距该点最近的点np
double ptolinedis (point p,line l, point &np)
{	//注意：np是线段l上到点p最近的点，不一定是垂足
	double r = relation (p, l);
	if(r < 0) return dis (p, np=l.s);
	if(r > 1) return dis (p, np=l.e);
	np = perpendicular (p, l);
	return dis (p, np);
}

double multi (point a, point b, point c)
{
	return (b.x-a.x)*(c.y-b.y) - (c.x-b.x)*(b.y-a.y);
}

bool judge (double a, double b)	
{
	if (fabs (a-b) < eps) return true;
	return a < b;
}

bool cmp (point a, point b)
{
	double cp = multi (P, a, b);
	if (fabs (cp) < eps) return dis (a, P) < dis (b, P);
	return  cp > 0;
}
//凸包模板，此模板生成的凸包不会出现3点共线
struct T2dHull{
	int n, K;
	point p[M], ch[M];
	void create ()
	{
		int i;
		for (i = 1; i < n; i++)
			if (p[i].y < p[0].y ||
				fabs (p[i].y-p[0].y) < eps && p[i].x < p[0].x)
			{ point tp = p[i]; p[i] = p[0]; p[0] = tp; }
		P = p[0];
		sort (p+1, p+n, cmp);
		//Graham_Scan
		ch[0] = p[0], ch[1] = p[1];
		K = 2;
		for (i = 2; i < n; i++)
		{
			while (K > 1 && judge (multi (ch[K-2], ch[K-1], p[i]), 0)) --K;
			ch[K++] = p[i];
		}
		ch[K] = ch[0];
	}
}h1, h2;

double cal (point a, point b, point c, point d)	//计算线段ab到线段cd的最小距离
{
	point pt;
	double res = ptolinedis (a, line(c,d), pt), tp;
	tp = ptolinedis (b, line(c,d), pt);
	if (tp < res) res = tp;
	tp = ptolinedis (c, line(a,b), pt);
	if (tp < res) res = tp;
	tp = ptolinedis (d, line(a,b), pt);
	if (tp < res) res = tp;
	return res;
}

int main ()
{
	int i;
	while (scanf ("%d%d", &h1.n, &h2.n), (h1.n||h2.n))
	{
		for (i = 0; i < h1.n; i++)
			scanf ("%lf%lf", &h1.p[i].x, &h1.p[i].y);
		for (i = 0; i < h2.n; i++)
			scanf ("%lf%lf", &h2.p[i].x, &h2.p[i].y);
		h1.create ();
		h2.create ();
		double res = -1;
		int p = 0;
	/*******枚举h1的边去卡h2的边*******/
	for (i = 0; i < h1.K; i++)
	{
		//正向卡
		while (cal (h1.ch[i], h1.ch[i+1], h2.ch[p+1], h2.ch[(p+2)%h2.K])
		< cal (h1.ch[i], h1.ch[i+1], h2.ch[p], h2.ch[p+1]))
			p = (p+1) % h2.K;
		//反向卡
		while (cal (h1.ch[i], h1.ch[i+1], h2.ch[(p-1+h2.K)%h2.K], h2.ch[p])
		< cal (h1.ch[i], h1.ch[i+1], h2.ch[p], h2.ch[p+1]))
			p = (p-1+h2.K) % h2.K;
		double tp = cal (h1.ch[i], h1.ch[i+1], h2.ch[p], h2.ch[p+1]);
		if (res < 0 || tp < res) res = tp;
	}
	/*******枚举h1的边去卡h2的边*******/
		printf ("%.6f\n", res);
	}
    return 0;
}