LINK

题意：在$10*10$的几何平面内，给出n条垂直x轴的线，且在线上开了两个口，起点为$(0, 5)$，终点为$(10, 5)$，问起点到终点不与其他线段相交的情况下的最小距离。

思路：将每个开口的两端点作为一个节点，再枚举点与点间能否直接到达（判相交），以此建图求最短路。

/** @Date    : 2017-07-11 16:17:31  * @FileName: POJ 1556 线段交+dijkstra 计算几何.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const double INF = 0x7f;const int N = 1e5+20;const double eps = 1e-8;struct Point{	double x, y;	Point(){}	Point(double xx, double yy){x = xx, y = yy;}	Point operator -(const Point &b) const	{		return Point(x - b.x, y - b.y);	}	double operator *(const Point &b) const 	{		return x * b.x + y * b.y;	}};double cross(Point a, Point b){	return a.x * b.y - a.y * b.x;}struct Line{	Point s, t;	Line(){}	Line(Point ss, Point tt){s = ss, t = tt;}};double distc(Point p1, Point p2){	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));}double xmult(Point p1, Point p2, Point p0)  {      return cross(p1 - p0, p2 - p0);  }  //判两点在线段异侧,点在线段上返回0  bool opposite_side(Point p1, Point p2, Line l)  {      return xmult(l.s, p1, l.t)*xmult(l.s, p2, l.t) < -eps;  }  bool JudgeInter(Line a, Line b)//判断线段相交 不包括端点及重合{	return opposite_side(a.s, a.t, b) && opposite_side(b.s, b.t, a);}Line l[200];Point p[200];double mp[200][200];double dis[200];bool vis[200];void dijkstra(int n){	MMF(vis);	MMI(dis);	dis[0] = 0;	vis[0] = 1;	queue<int>q;	q.push(0);	while(!q.empty())	{		int nw = q.front();		q.pop();		for(int i = 0; i < n; i++)		{			double dic = dis[nw] + mp[nw][i];			if(dis[i] > dic)				dis[i] = dic;		}		double mi = INF;		int np = 0;		for(int i = 0; i < n; i++)			if(!vis[i] && mi > dis[i])				mi = dis[i], np = i;		if(mi == INF)			break;		q.push(np);		vis[np] = 1;	}}int n;int main(){	while(~scanf("%d", &n) && n!=-1)	{		int cntl = 0;		int cntp = 0;		p[cntp++] = Point(0, 5.0000);		double x, a, b, c, d;		for(int i = 0; i < n; i++)		{			scanf("%lf%lf%lf%lf%lf", &x, &a, &b, &c, &d);			p[cntp++] = Point(x, 0.000);			p[cntp++] = Point(x, a);			l[cntl++] = Line(p[cntp - 2], p[cntp - 1]);			p[cntp++] = Point(x, b);			p[cntp++] = Point(x, c);			l[cntl++] = Line(p[cntp - 2], p[cntp - 1]);			p[cntp++] = Point(x, d);			p[cntp++] = Point(x, 10.0000);			l[cntl++] = Line(p[cntp - 2], p[cntp - 1]);		}		p[cntp++] = Point(10.0000, 5.0000);		/////		for(int i = 0; i < cntp; i++)//枚举任意两个点间是否能直接到达 		{			for(int j = 0; j < cntp; j++)			{				if(j == i)					continue;				Line tmp = Line(p[i], p[j]);				int flag = 0;				for(int k = 0; k < cntl; k++)				{					if(JudgeInter(tmp, l[k]))//判断是否与线段相交					{						mp[i][j] = INF;						flag = 1;						break;					}				}				if(!flag)					mp[i][j] = distc(p[i], p[j]);			}		}		dijkstra(cntp);		/*for(int i = 0; i < cntp; i++)			cout << dis[i] << endl;*/		printf("%.2lf\n", dis[cntp - 1]);	}    return 0;}

POJ 1556 The Doors 线段交 dijkstra