链接 The Doors

题意

从 ( 0 , 5 ) (0,5) (0,5) 位置走到 ( 10 , 5 ) (10,5) (10,5)，有 n n n 个垂直于 x x x 轴的墙壁，每个墙壁都会有两个门洞。下面的图片显示出了一个墙体及最短路径。

思路

首先我们把每两个点连一条边，判断边是否和墙体相交，如果不相交就连边，相交就不连；

最后跑一遍 d i j k s t r a dijkstra dijkstra 最短路就可以；

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define mes memset
#define mec memcpy
#define pb push_back
#define be(x) (x).begin(), (x).end()
#define cl(x) memset((x), 0, sizeof (x))
#define sz(x) (int)(x).size()
#define inf 99999999999.0

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll,ll> PLL;


const double eps = 1e-8;
const int N = 1010;
const int null = 0x3f3f3f3f,INF = 1e9;
const ll mod = 998244353;

struct Point {
	double x, y;
};

struct Line {
	Point a, b;
};

int n, pnum;
vector<Point> p;
vector<Line> l;
double dist[N][N];
double d[N];
bool st[N];

Line add(Point a, Point b) {
	Line c;
	c.a = a;
	c.b = b;
	return c;
}

double mul(Point a, Point b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

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

bool check_Line(Point a, Point b, Point c, Point d) {
	return (cross(a, c, b) * cross(a, b, d) > 0) && (cross(c, a, d) * cross(c, d, b) > 0);
}

void init() {
	for (int i = 0; i <= pnum; i ++) {
		for (int j = i; j <= pnum; j ++) {
            if (i == j) {
                dist[i][j] = dist[j][i] = 0.0;
                continue;
            }
			int left = (i + 1) / 2, right = (j + 1) / 2;
			bool flag = false;
			for (int k = left + 1; k < right; k ++) {
				if (check_Line(p[i], p[j], l[k].a, l[k].b)) {
					flag = true;
					break;
				}
			}
            
			if (flag) dist[i][j] = dist[j][i] = inf;
			else dist[i][j] = dist[j][i] = mul(p[i], p[j]);
		}
	}
}

void dijkstra()
{
    for (int i = 0; i <= pnum; i ++) d[i] = inf, st[i] = false;

    d[0] = 0.0;

    for(int i = 0;i <= pnum;i ++)
    {
        int t = -1;
        for(int j = 0;j <= pnum;j ++)
        {
            if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
        }

        for(int j = 0;j <= pnum;j ++)
        {
            d[j] = min(d[j], d[t] + dist[t][j]);
        }

        st[t] = true;
    }

}


int main() {
	while (cin >> n) {
		if (n == -1) break;
		p.clear(), l.clear();
		pnum = 0;
		double x, y_1, y2, y3, y4;

		Point a,b;
		a.x = 0, a.y = 5.0, pnum ++;
		p.pb(a);

		for (int i = 1; i <= n; i ++) {
			cin >> x >> y_1 >> y2 >> y3 >> y4;
			a.x = x, b.x = x;
			a.y = 0, b.y = y_1;
			pnum += 2;
			p.pb(a), p.pb(b);
			l.pb(add(a, b));

			a.y = y2, b.y = y3;
			pnum += 2;
			p.pb(a), p.pb(b);
			l.pb(add(a, b));

			a.y = y4, b.y = 10.0;
			pnum += 2;
			p.pb(a), p.pb(b);
			l.pb(add(a, b));
		}

		a.x = 10.0, a.y = 5.0;
		p.pb(a);

		init();
		dijkstra();
		printf("%.2lf\n", d[pnum]);
	}
}

END