【最短路+dijkstra+有难度】杭电 hdu 1245 Saving James Bond

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1245
	Name  : 1245 Saving James Bond

	Date  : Tuesday, January 17, 2012
	Time Stage : 8 hours

	Result: 
5268663	2012-01-17 16:34:56	Accepted	1245
203MS	320K	4753 B
C++	pyy


Test Data :

Review :
耗时8小时左右，十次提交，终于AC，也算是我做的少有的大题目了，唔，
以后要多做一些大题目啊。

据说此题卡精度……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std ;

#define MEM(a, v)	memset (a, v, sizeof (a))
#define min(x, y)	((x) < (y) ? (x) : (y))
#define max(x, y)	((x) > (y) ? (x) : (y))
#define SQR(x)		((x)*(x))

#define EPS			1e-8
#define GT(x, y)	(((x) - (y)) > EPS)			// 大于
#define EQ(x, y)	(fabs((x) - (y)) <= EPS)	// 等于
#define LT(x, y)	GT(y, x)					// 小于
#define GET(x, y)	(!LT(x, y))					// >=
#define LET(x, y)	(!GT(x, y))					// <=

#define INF		0x3f3f3f3f
#define MAXN	103
#define DELTA	50
#define RADIUS	7.5

inline double getdist (int i, int j) ;

typedef struct tagPOINT {
	int x, y ;
} POINT ;

struct EDGE {
	int des ;
	double dis ;
	EDGE () {}
	EDGE (int e, double ds) : 
		des(e), dis(ds) {}
};

bool	used[MAXN] ;

int		n, cnt ;
int		step[MAXN] ;

double	d ;
double	dist[MAXN] ;

vector<EDGE>	graph[MAXN] ;	// store edges

POINT	map[MAXN] ;

void init ()
{
	int i ;
	for (i = 0 ; i < MAXN ; ++i)
		graph[i].clear () ;
	memset (map, 0, sizeof (map)) ;
}

inline double getdist (double x1, double y1, double x2, double y2)
{
	return sqrt (SQR(x1-x2) + SQR(y1-y2)) ;
}

inline double getdist (int i, int j)
{
	return getdist (map[i].x, map[i].y, map[j].x, map[j].y) ;
}

inline double tostart (int i)
{
	// RADIUS : 别忘了小岛是有半径的，一开始把 diameter 看成是半径了，晕死啊
	return getdist (map[i].x, map[i].y, DELTA, DELTA) - RADIUS;
}

inline double toend (int i)
{
	return min (
		min (map[i].x, map[i].y), 
		min (abs (100-map[i].x), abs(100-map[i].y))) ;
}

void makegraph ()
{
	int i, j ;
	double s, e ;
	for (i = 1 ; i <= n ; ++i)
	{
		// 到小岛的距离
		s = tostart (i) ;
		// 到岸边的距离
		e = toend (i) ;
		// 从小岛可以直接跳上的点
		if (GT(s, 0) && GET(d, s))
			graph[0].push_back(EDGE(i, s)) ;
		// 可以直接跳到岸上的点
		if (GT(e, 0) && GET(d, e))
			graph[i].push_back(EDGE(n+1, e)) ;
	}

	// 各点到各点的可行的边
	for (i = 1 ; i <= n ; ++i)
		for (j = 1 ; j <= n ; ++j)
		{
			if (i == j)
				continue ;
			s = getdist (i, j) ;
			if (GET(d, s))
			{
				graph[i].push_back(EDGE(j, s)) ;
			}
		}
}

// dijkstra 中处理的各点都应具有平等的身份，这样才能方便处理，
// 像 “小岛” 和 “岸边”这种特殊情况要想办法预先转化为与“点”
// 一样的角色
void dijkstra (const int start, const int end)
{
	int i, j, id ;
	int iMinPath ;
	double MinPath, s ;

	MEM (step, 0) ;
	MEM (used, 0) ;
	
	for (i = start ; i <= end ; ++i)
		dist[i] = INF * 1.0 ;

	// 从小岛可以直接跳上的点
	for (i = 0 ; i < graph[start].size() ; ++i)
	{
		id = (graph[start][i]).des ;
		dist[id] = graph[start][i].dis ;
		step[id] = 1 ;
	}

	for (j = start ; j <= end ; ++j)
	{
		iMinPath = 0 ;
		MinPath = INF * 1.0 ;

		for (i = start ; i <= end ; ++i)
			if (!used[i] && dist[i] < MinPath)
			{
				iMinPath = i ;
				MinPath = dist[i] ;
			}

		used[iMinPath] = 1 ;

		for (i = 0 ; i < graph[iMinPath].size() ; ++i)
		{
			// 能从 iMinPath 到达的点 id
			id = graph[iMinPath][i].des ;
			// 原路径加上 边(iMinPath, id) 的距离
			s = dist[iMinPath] + graph[iMinPath][i].dis ;

			if (!used[id] && LT(s, dist[id]))
			{
				dist[id] = s ;
				step[id] = step[iMinPath] + 1 ;
			}
		}
	}
}

int main ()
{
	int i ;
	int x, y ;
	while (~scanf ("%d%lf", &n, &d))
	{
		init () ;
		for (i = 1 ; i <= n ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			// DELTA 的意思，是把整幅图向右向上各平移了 DELTA 个单位
			map[i].x = x + DELTA ;
			map[i].y = y + DELTA ;
		}

		// 可以一步直接跳出来的，直接输出
		// 本来是想直接输出 d 而不是 50-RADIUS 的，
		// 但考虑到 James Bond 应该不至于每一步都固定吧
		if (GET(d, 50-RADIUS))
			printf ("%.2lf %d\n", 50-RADIUS, 1) ;
		else
		{
			// 建图，处理小岛和岸边这两大麻烦。
			// 参考大牛的做法，把这两处处理成两点：0 和 n+1
			// 其实我感觉本题的难处可能就是处理这两点的问题上
			// 因为一开始想不到什么好办法，于是在 dijkstra 中处理
			// 结果弄得很麻烦，因为问题分散了，一开始没有建好图，
			// 后面就要步步惊心地小心注意区分好 "小岛、岸边与各点"
			// 总之一句话：把问题在源头处理好，就不会污染整个流程了！
			makegraph () ;
			dijkstra(0, n+1) ;
			if (LT(dist[n+1], INF * 1.0))
				printf ("%.2lf %d\n", dist[n+1], step[n+1]) ;
			else
				puts ("can't be saved") ;
		}
	}
	return 0 ;
}