黑书上的一道例题：如果走最短路则会碰到点，除非中间没有障碍。
这样把能一步走到的点两两连边，然后跑SPFA即可。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100003
using namespace std;
struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
inline int dcmp(double a) {
return (fabs(a) < 1e-6) ? 0 : (a < 0 ? -1 : 1);
}
Point operator - (Point a, Point b) {
return Point(a.x - b.x, a.y - b.y);
}
bool operator == (Point a, Point b) {
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
inline double Cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
inline double Dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
inline bool jiao(Point d1, Point d2, Point d3, Point d4) {
return (dcmp(Cross(d4 - d3, d1 - d3)) ^ dcmp(Cross(d4 - d3, d2 - d3))) == -2 &&
(dcmp(Cross(d2 - d1, d3 - d1)) ^ dcmp(Cross(d2 - d1, d4 - d1))) == -2;
}
inline int bjiao(Point d1, Point d2, Point d3) {
if (d1 == d2 || d1 == d3)
return 1;
if (dcmp(Cross(d2 - d1, d3 - d1)) == 0 && dcmp(Dot(d2 - d1, d3 - d1)) == -1)
return 1;
return 0;
}
inline double dis(Point d1, Point d2) {
return sqrt((d2.y - d1.y) * (d2.y - d1.y) + (d2.x - d1.x) * (d2.x - d1.x));
} struct nodeline {
Point a, b;
nodeline(Point _a = (0, 0) , Point _b = (0, 0)) : a(_a), b(_b) {}
} line[N]; struct node {
int nxt, to;
double w;
} E[N << 1]; Point a[N];
int n, cnt, lcnt, point[N], dd, q[N];
double nowx, nowy, nowy2, dist[N];
bool vis[N]; inline void ins(int x, int y, double z) {++dd; E[dd].nxt = point[x]; E[dd].to = y; E[dd].w = z; point[x] = dd;}
inline double spfa(int S, int T) {
memset(dist, 127, sizeof(dist));
memset(vis, 0, sizeof(vis));
int head = 0, tail = 1;
q[1] = S;
vis[S] = 1;
dist[S] = 0;
while (head != tail) {
++head; if (head >= N) head %= N;
int u = q[head];
vis[u] = 0;
for(int tmp = point[u]; tmp; tmp = E[tmp].nxt) {
int v = E[tmp].to;
if (dist[u] + E[tmp].w < dist[v]) {
dist[v] = dist[u] + E[tmp].w;
if (!vis[v]) {
++tail; if (tail >= N) tail %= N;
q[tail] = v;
vis[v] = 1;
}
}
}
}
return dist[T];
} inline bool check(Point d1, Point d2) {
for(int i = 1; i <= lcnt; ++i)
if (jiao(d1, d2, line[i].a, line[i].b))
return 0;
return 1;
} int main() {
scanf("%d", &n);
while (n != -1) {
cnt = 2;
lcnt = 0;
a[1].x = 0;
a[1].y = 5;
a[2].x = 10;
a[2].y = 5;
for(int i = 1; i <= n; ++i) {
scanf("%lf", &nowx);
scanf("%lf", &nowy);
a[++cnt] = Point(nowx, nowy);
line[++lcnt] = nodeline(Point(nowx, 0), a[cnt]);
scanf("%lf", &nowy);
a[++cnt] = Point(nowx, nowy);
scanf("%lf", &nowy2);
a[++cnt] = Point(nowx, nowy2);
line[++lcnt] = nodeline(a[cnt - 1], a[cnt]);
scanf("%lf", &nowy);
a[++cnt] = Point(nowx, nowy);
line[++lcnt] = nodeline(a[cnt], Point(nowx, 10));
} memset(point, 0 , sizeof(point));
dd = 0;
for(int i = 1; i <= cnt; ++i)
for(int j = i + 1; j <= cnt; ++j)
if (check(a[i], a[j]))
ins(i, j, dis(a[i], a[j]));
for(int i = 1; i <= cnt; ++i)
if (i != 2 && check(a[i], a[2]))
ins(i, 2, dis(a[i], a[2]));
printf("%.2lf\n", spfa(1,2));
scanf("%d", &n);
}
return 0;
}
清明节机房也放假啊滚来滚去……~(～o￣▽￣)～o 。。。滚来滚去……o～(＿△＿o～) ~。。。