Cockchaf.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.TreeMap;
 
 
class Edge implements Comparable<Edge>
{
	public Double t;
	public int dx, dy, dz;
 
	@Override
	public int compareTo(Edge arg0) {
		return t.compareTo(arg0.t);
	}
 
	public Edge(double t, int dx, int dy, int dz) {
		this.t = t;
		this.dx = dx;
		this.dy = dy;
		this.dz = dz;
	}
 
	public double angleTo(Edge e) {
		return Math.acos(
			(dx * e.dx + dy * e.dy + dz * e.dz)/
			(Math.sqrt(dx*dx+dy*dy+dz*dz)*Math.sqrt(e.dx*e.dx+e.dy*e.dy+e.dz*e.dz)
			)
		);
	}
}
 
class Node
{
	public int x, y, z;
	public LinkedList<Node> nbh;
	public boolean end, visited;
 
	@Override
	public int hashCode()
	{
		return x ^ y ^ z;
	};
 
	@Override
	public boolean equals(Object arg0) 
	{
		if (arg0 instanceof Node)
		{
			Node a = (Node)arg0;
			return (x == a.x) && (y == a.y) && (z == a.z);
		}
		return false;
	}
 
	public Node(int x, int y, int z, boolean end)
	{
		this.x = x;
		this.y = y;
		this.z = z;
		this.end = end;
		visited = false;
 
		nbh = new LinkedList<Node>();
	}
 
	public double distanceTo(Node node)
	{
		int dx = node.x - x;
		int dy = node.y - y;
		int dz = node.z - z;
		return Math.sqrt(dx*dx + dy*dy + dz*dz);
	}
 
	public Edge edgeTo(Node node, double t)
	{
		int dx = node.x - x;
		int dy = node.y - y;
		int dz = node.z - z;
		return new Edge(t, dx, dy, dz);
	}
}
 
public class Cockchaf {
 
	public static double time(double dist, double speed)
	{
		return dist / speed;
	}
 
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
 
		String s;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		HashMap<Node, Node> nMap = new HashMap<Node, Node>();
		String[] ss;
		int n, ssp;
		double dist, t, angle, asp;
		Edge e, e2;
		Node a, b, start;
		TreeMap<Edge, Node> pq = new TreeMap<Edge, Node>();
 
		while (true)
		{
			s = br.readLine();
			if (s == null) break;
 
			ss = s.split(" ");
 
			n = Integer.parseInt(ss[0]);
			ssp = Integer.parseInt(ss[1]);
			asp = Math.PI * Integer.parseInt(ss[2])/180.0;
 
			s = br.readLine();
			ss = s.split(" ");
 
			a = new Node(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]), Integer.parseInt(ss[2]), false);
			b = new Node(Integer.parseInt(ss[3]), Integer.parseInt(ss[4]), Integer.parseInt(ss[5]), true);
			start = a;
 
			nMap.put(a, a);
			nMap.put(b, b);
 
			for (int i = 0; i < n; i++)
			{
				s = br.readLine();
				ss = s.split(" ");
 
				a = new Node(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]), Integer.parseInt(ss[2]), false);
				b = new Node(Integer.parseInt(ss[3]), Integer.parseInt(ss[4]), Integer.parseInt(ss[5]), false);
 
				if (nMap.containsKey(a)) a = nMap.get(a);
				else nMap.put(a, a);
 
				if (nMap.containsKey(b)) b = nMap.get(b);
				else nMap.put(b, b);
 
				a.nbh.addLast(b);
				b.nbh.addLast(a);
			}
 
			a = start;
			a.visited = true;
			for (Node node : a.nbh)
			{
				dist = a.distanceTo(node);
				pq.put(a.edgeTo(node, time(dist, ssp)), node);
			}
 
			while (!pq.isEmpty())
			{
				e = pq.firstKey();
				a = pq.remove(e);
				t = e.t;
 
				if (a.visited) continue;
				a.visited = true;
 
				if (a.end)
				{
					DecimalFormat nf = new DecimalFormat("#.####");
					System.out.println(nf.format(e.t).replace(',', '.'));
				}
 
				for (Node node : a.nbh)
				{
					e2 = a.edgeTo(node, t);
					dist = a.distanceTo(node);
					angle = e.angleTo(e2);
					e2.t += time(angle, asp) + time(dist, ssp);
					pq.put(e2, node);
				}
			}
		}
	}
 
}