【旋转卡壳】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-8struct 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的最短距离,并返回线段上距该点最近的点npdouble 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);returncp > 0;}//凸包模板，此模板生成的凸包不会出现3点共线struct T2dHull{int n, K;point p, ch;void create (){int i;for (i = 1; i < n; i++)if (p.y < p.y ||fabs (p.y-p.y) < eps && p.x < p.x){ point tp = p; p = p; p = tp; }P = p;sort (p+1, p+n, cmp);//Graham_Scanch = p, ch = p;K = 2;for (i = 2; i < n; i++){while (K > 1 && judge (multi (ch, ch, p), 0)) --K;ch = p;}ch = ch;}}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.x, &h1.p.y);for (i = 0; i < h2.n; i++)scanf ("%lf%lf", &h2.p.x, &h2.p.y);h1.create ();h2.create ();double res = -1;int p = 0;/*******枚举h1的边去卡h2的边*******/for (i = 0; i < h1.K; i++){//正向卡while (cal (h1.ch, h1.ch, h2.ch, h2.ch[(p+2)%h2.K])< cal (h1.ch, h1.ch, h2.ch, h2.ch))p = (p+1) % h2.K;//反向卡while (cal (h1.ch, h1.ch, h2.ch[(p-1+h2.K)%h2.K], h2.ch)< cal (h1.ch, h1.ch, h2.ch, h2.ch))p = (p-1+h2.K) % h2.K;double tp = cal (h1.ch, h1.ch, h2.ch, h2.ch);if (res < 0 || tp < res) res = tp;}/*******枚举h1的边去卡h2的边*******/printf ("%.6f\n", res);} return 0;}
页:
[1]