2041.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2041 on 2006-06-02 at 23:38:07 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int WN = 1024;
const int INF = 1 << 30;

class Wall {
public:
	int x1, y1, x2, y2, k;
	void make();
	int go(const Wall&) const;
};
void Wall::make() {
	int l; scanf("%d %d %d", &x1, &y1, &l);
	k = (l > 0); l = abs(l);
	if(k == 0) { x2 = x1; y2 = y1+l; }
	else { x2 = x1+l; y2 = y1; }
}
int Wall::go(const Wall& w) const {
	if(k != w.k) {
		int dis = 0, l, r, m, d, u, t;
		if(x1 == x2) { m = x1; l = w.x1; r = w.x2; }
		else { m = w.x1; l = x1; r = x2; }
		if(y1 == y2) { t = y1; d = w.y1; u = w.y2; }
		else { t = w.y1; d = y1; u = y2; }
		if(m < l || m > r) dis += min((m-l)*(m-l), (m-r)*(m-r));
		if(t < d || t > u) dis += min((t-d)*(t-d), (t-u)*(t-u));
		return dis;
	} else {
		int dis = 0, d1, u1, d2, u2, l;
		if(k == 0) { l = abs(x1-w.x1); d1 = y1; u1 = y2; d2 = w.y1; u2 = w.y2; }
		else { l = abs(y1-w.y1); d1 = x1; u1 = x2; d2 = w.x1; u2 = w.x2; }
		if(u2 < d1) dis = (d1-u2)*(d1-u2);
		else if(u1 < d2) dis = (d2-u1)*(d2-u1);
		return dis+l*l;
	}
}

int n;
Wall wall[WN];

int dijkstra(int, int);

int main()
{
	int i;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) wall[i].make();
		printf("%.2lf\n", sqrt(dijkstra(0, 1)*1.0));
	}
	
	return 0;
}

int dijkstra(int src, int dis)
{
	int d[WN], i; bool vst[WN] = { false };
	for(i = 0; i < n; i++) d[i] = INF;
	d[src] = 0;
	while(true) {
		int md = INF, mi;
		for(i = 0; i < n; i++)
			if(!vst[i] && md > d[i]) { md = d[i]; mi = i; }
		if(mi == dis) break;
		vst[mi] = true;
		for(i = 0; i < n; i++) {
			if(vst[i]) continue;
			int dw = wall[mi].go(wall[i]);
			d[i] = min(d[i], max(dw, d[mi]));
		}
	}
	return d[dis];
}