隐匿踪迹

描述

在数码世界的某次战争中，年轻的狮子兽收到了一封密函，密函中指出需要让他从当前坐标赶往另一个坐标去狙击敌人的精英部队。但是狮子兽知道，整个战场都有可能被敌方的飞行兽从上往下侦查到，因此需要注意隐匿自己的行踪。

狮子兽虽然年轻，但他对战场非常了解，他知道在战场上存在N个无法被飞行兽侦查到的浮空圆盘，只要在浮空圆盘内部（包括圆盘边界，下同）就不会被飞行兽侦查到（浮空圆盘可能重叠）。

现在狮子兽想要从当前坐标前往指定坐标（假设其行进速度恒定，1单位时间行进1单位距离），但是为了减少暴露自己的可能，所以想使不在浮空圆盘内部的时间尽可能少。

注意：整个战场是一个连续二维坐标平面，地势平缓，且狮子兽的行进可以是任何方向、可以是直线也可以是曲线。

输入

每个输入文件中一组数据。 第一行一个正整数N（1<=N<=1000），表示浮空圆盘的个数。 
接下来N行，每行三个整数x, y, r（-1000<=x,y<=1000、0<=r<=10），分别代表浮空圆盘的坐标(x,y)和半径r。 
最后分两行给出狮子兽的当前坐标和目的坐标，每行两个整数x, y（-1000<=x,y<=1000）。 

输出格式 
输出不在浮空圆盘内部的最少时间（即不得不暴露在飞行兽侦查下的最少时间）。结果精度保留两位小数。 

输出

输出不在浮空圆盘内部的最少时间（即不得不暴露在飞行兽侦查下的最少时间）。结果精度保留两位小数。

样例输入1

1
0 0 1
2 0
0 2

样例输出1

2.00

import java.util.Scanner;

public class Main {		
	//飞盘坐标及半径
	static class Point {
		int x, y, r;
		
		Point(int xx, int yy, int rr) {
			x = xx;
			y = yy;
			r = rr;
		}
	}
	static Scanner input = new Scanner(System.in);
	static double[][] dis;    //边权值
	static final double INF = Double.MAX_VALUE;
	static int N;
	static Point[] point;
	static double minDis[];   //最小边权值
	//获得每个飞盘信息
	public static void getPoint() {
		point = new Point[N];
		for (int i = 1; i < N-1; i++)
			point[i] = new Point(input.nextInt(), input.nextInt(), input.nextInt());
		point[0] = new Point(input.nextInt(), input.nextInt(), 0); //起始点，半径为0
		point[N-1] = new Point(input.nextInt(), input.nextInt(), 0);  //目标点， 半径为0
	}
	
	public static double getDistance(int i, int j) {
		//(x*x + y*y)^0.5 - r1 - r2
		double tmp = Math.pow(Math.pow((point[i].x - point[j].x), 2) + Math.pow((point[i].y - point[j].y), 2), 0.5) - point[i].r - point[j].r;
		return Math.max(tmp, 0.0);
	}
	
	public static void Dijksdra(int src) {  
		boolean[] vis = new boolean[N+1];
		minDis = new double[N+1];
		for (int i = 1; i <= N; i++) {
			minDis[i] = INF;
			vis[i] = false;
		}
		minDis[src] = 0.0;
		for (int i = 1; i <= N; i++) {
			int u = -1;
			for (int j = 1; j <= N; ++j)
				if (!vis[j] && (u == -1 || minDis[u] > minDis[j])) u = j;
			vis[u] = true;
			for (int j = 1; j <= N; ++j) 
				minDis[j] = Math.min(minDis[u] + dis[u][j], minDis[j]);
		}
	}
	
	public static void main(String[] args) {
		while (input.hasNext()) {
			N = input.nextInt();
			N += 2;
			dis = new double[N+1][N+1];
			getPoint();
			for (int i = 1; i <= N; ++i)
				for (int j = 1; j < i; ++j)
					dis[i][j] = dis[j][i] = getDistance(i-1, j-1);		
			Dijksdra(1);
			System.out.printf("%.2f\n", minDis[N]);
		}
	}

}