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;
}
?