poj1556

maksyuki 发表于 oj 分类，标签: 图论-最短路, 计算几何-点线面\点积\叉积

29 1月 2016

The Doors

You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.

Input

The input data for the illustrated chamber would appear as follows.

2
4 2 7 8 9
7 3 4.5 6 7

The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.

Output

The output should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.

Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

Sample Output

10.00

10.06

Source

Mid-Central USA 1996

题目类型：线段相交+最短路

算法分析：由题易知只有每次走门的端点而不是走中间才能保证两点之间的边是最短的。枚举任意两点构造线段判断是否与图中的竖墙的分隔线段相交，分类讨论之后在满足条件的点之间连边，最后跑一个最短路即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 18:24:35
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 66;

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1; 
}

struct Point
{
	double x, y;
	Point () {}
	Point (double xx, double yy) : x (xx), y (yy) {}

	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	double operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x;
	}

	double operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

Point p[maxn];
Line l[maxn];
int n;
double edge[maxn][maxn], dis[maxn];;

double Dist (Point p1, Point p2)
{
	return sqrt ((p2 - p1) * (p2 - p1));
}

bool inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

void Dij (int s)
{
	fill (dis, dis + maxn, INF);
	dis[s] = 0;
	priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;
	qu.push (pair <int, double> (s, 0));
	while (!qu.empty ())
	{
		pair <int, double> tt = qu.top (); qu.pop ();
		int ta = tt.first;
		double tb = tt.second;
		if (sgn (dis[ta] - tb) < 0) continue;
		for (int i = 1; i <= 4 * n + 2; i++)
			if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])
			{
				dis[i] = edge[ta][i] + dis[ta];
				qu.push (pair <int, double> (i, dis[i]));
			}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == -1) break;
		
		p[1] = Point (0, 5);
		p[4*n+2] = Point (10, 5);
		int tota = 1, totb = 0;
		for (int i = 1; i <= n; i++)
		{
			double x, y;
			scanf ("%lf", &x);
			for (int j = 1; j <= 4; j++)
			{
				scanf ("%lf", &y);	
				p[++tota] = Point (x, y);	
				if (j == 1)
					l[++totb] = Line (Point (x, 0), Point (x, y));
				else if (j == 3)
					l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));
				else if (j == 4)
					l[++totb] = Line (Point (x, y), Point (x, 10));
			}	
		}
		
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				edge[i][j] = INF;

		for (int i = 1; i <= 4 * n + 2; i++)
			for (int j = i + 1; j <= 4 * n + 2; j++)
			{
				int cnt = 0;
				for (int k = 1; k <= 3 * n; k++)
				{
					Line tt = Line (p[i], p[j]);
					if (inter (tt, l[k]))
						cnt++;
				}
				if (i == 1 && j < 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i == 1 && j == 4 * n + 2 && cnt == 0) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j < 4 * n + 2 && cnt == 2) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j == 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
			}
		
		for (int i = 1; i <= n; i++)
		{
			int ta = 4 * i - 2, tb =  ta + 1;
			edge[ta][ta+2] = edge[ta+2][ta] = INF;
			edge[tb][tb+2] = edge[tb+2][tb] = INF;
		}
		Dij (1);
		//for (int i = 1; i <= 4 * n + 2; i++)
	//	{
	//		for (int j = 1; j <= 4 * n + 2; j++)
	//			if (edge[i][j] < INF)
	//				cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;
	//	}
		printf ("%.2f\n", dis[4*n+2]);
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

/*************************************************

Author :supermaker

Created Time :2016/1/29 18:24:35

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 66;

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

struct Point

{

double x, y;

Point () {}

Point (double xx, double yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

double operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

double operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

Point p[maxn];

Line l[maxn];

int n;

double edge[maxn][maxn], dis[maxn];;

double Dist (Point p1, Point p2)

{

return sqrt ((p2 - p1) * (p2 - p1));

}

bool inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;

}

void Dij (int s)

{

fill (dis, dis + maxn, INF);

dis[s] = 0;

priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;

qu.push (pair <int, double> (s, 0));

while (!qu.empty ())

{

pair <int, double> tt = qu.top (); qu.pop ();

int ta = tt.first;

double tb = tt.second;

if (sgn (dis[ta] - tb) < 0) continue;

for (int i = 1; i <= 4 * n + 2; i++)

if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])

{

dis[i] = edge[ta][i] + dis[ta];

qu.push (pair <int, double> (i, dis[i]));

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

if (n == -1) break;

p[1] = Point (0, 5);

p[4*n+2] = Point (10, 5);

int tota = 1, totb = 0;

for (int i = 1; i <= n; i++)

{

double x, y;

scanf ("%lf", &x);

for (int j = 1; j <= 4; j++)

{

scanf ("%lf", &y);

p[++tota] = Point (x, y);

if (j == 1)

l[++totb] = Line (Point (x, 0), Point (x, y));

else if (j == 3)

l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));

else if (j == 4)

l[++totb] = Line (Point (x, y), Point (x, 10));

}

for (int i = 0; i < maxn; i++)

for (int j = 0; j < maxn; j++)

edge[i][j] = INF;

for (int i = 1; i <= 4 * n + 2; i++)

for (int j = i + 1; j <= 4 * n + 2; j++)

{

int cnt = 0;

for (int k = 1; k <= 3 * n; k++)

{

Line tt = Line (p[i], p[j]);

if (inter (tt, l[k]))

cnt++;

}

if (i == 1 && j < 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i == 1 && j == 4 * n + 2 && cnt == 0)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j < 4 * n + 2 && cnt == 2)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j == 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

}

for (int i = 1; i <= n; i++)

{

int ta = 4 * i - 2, tb = ta + 1;

edge[ta][ta+2] = edge[ta+2][ta] = INF;

edge[tb][tb+2] = edge[tb+2][tb] = INF;

}

Dij (1);

//for (int i = 1; i <= 4 * n + 2; i++)

// {

// for (int j = 1; j <= 4 * n + 2; j++)

// if (edge[i][j] < INF)

// cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;

// }

printf ("%.2f\n", dis[4*n+2]);

}

return 0;

}

poj3111

poj2653

超客的水墨烟雨

poj1556

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30