POJ 1556 The Doors 线段交 dijkstra

题意：在$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

最新文章

热门文章