Problem: Milky Way

Milky Way

English text is not available in this practice contest.

The Milky Way Transportation Corporation is a travel agency that plans and manages interstellar travel tours. The Milky Way Transportation Corporation is planning a project called "Milky Way Crossing Orihime Hikoboshi Experience Tour". This tour departs from Vega in Lyra and travels around the stars to Altair in Aquila. You are an employee of the Milky Way Transportation Corporation and are responsible for choosing the route of the tour.

For simplicity, the Milky Way shall be on two-dimensional coordinates, and the stars shall be represented by pentagrams. The spacecraft used for the tour is equipped with a special engine and can move on the pentagram line segment without energy. On the other hand, when moving between pentagrams, energy proportional to the distance is required.

In recent years, sales of the Milky Way Transportation Corporation have been sluggish, and there is a pressing need to save various necessary expenses such as energy costs for spacecraft. Your job is to find a route that minimizes the sum of interstellar travel distances when moving from Vega to Altair, and write a program that outputs that sum.

Note that when moving from one pentagram to another that is contained within it, if the pentagrams are not in contact with each other, they are treated as interstellar movements.

Figure D-1 illustrates the third Sample Input. In the figure, the red line segment represents the part of the interstellar movement of the route that minimizes the total interstellar movement distance.

<image>

Figure D-1: Movement between stars

Input

The input consists of one or more datasets. One dataset has the following format:

> N M L
> x1 y1 a1 r1
> x2 y2 a2 r2
> ...
> xN yN aN rN
>

The first line of each test case consists of the integers N, M, L, where N is the number of stars (1 ≤ N ≤ 100), M is the Vega number (1 ≤ M ≤ N), and L is the Altair number (1 ≤ M ≤ N). Represents 1 ≤ L ≤ N). Information on each star is given in the following N lines. Each row consists of four integers, xi, yi, ai, and ri, where xi is the x-coordinate of the center of the i-th star (0 ≤ xi ≤ 1,000) and yi is the y-coordinate of the center of the i-th star (0 ≤ yi). ≤ 1,000), ai is the angle formed by the straight line connecting the center coordinates of the i-th star and the tip of the star with the y-axis (0 ≤ ai <72), and ri is from the center coordinates of the i-th star to the tip of the star. The length (1 ≤ ri ≤ 1,000). The end of the input is represented by a line containing three zeros.

The star on the left in Figure D-2 represents the star with x = 5, y = 10, a = 0, r = 5, and the star on the right is x = 15, y = 10, a = 30, r = 5. Represents the star of.

<image>

Figure D-2: Star example

Output

For each input, output the minimum total interstellar movement distance required to move from Vega to Altair on one line. The output must not have an error greater than 0.000001.

Sample Input


1 1 1
5 5 0 5
2 1 2
5 5 0 5
15 5 0 5
3 2 3
15 15 0 5
5 5 10 5
25 25 20 5
0 0 0


Output for Sample Input


0.00000000000000000000
0.48943483704846357796
9.79033725601359705593






Example

Input




Output

Solution (in JAVA):

Solution:

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class Main {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	class Star {
		int[] radian = {90, 234, 18, 162, 306};
		Point2D.Double[] points = new Point2D.Double[5];
		Line2D.Double[] lines = new Line2D.Double[5];
		
		Star(int x, int y, int a, int r) {
			for (int i = 0; i < points.length; i++) {
				points[i] = new Point2D.Double(r * Math.cos((radian[i] + a) / 360.0 * 2 * Math.PI) + x, r * Math.sin((radian[i] + a) / 360.0 * 2 * Math.PI) + y);
			}
			for (int i = 0; i < lines.length; i++) {
				lines[i] = new Line2D.Double(points[i], points[(i+1) % 5]);
			}
		}
		
		public String toString() {
			String s = "";
			for (int i = 0; i < points.length; i++) {
				s += "(" + points[i].x + " " + points[i].y + ")\n";
			}
			return s;
		}
	}
	
	double culcDist(Star s1, Star s2) {
		double res = Double.MAX_VALUE;
		for (Line2D.Double line1 : s1.lines) {
			for (Line2D.Double line2 : s2.lines) {
				if (line1.intersectsLine(line2)) return 0;
			}
		}
		
		for (Line2D.Double line1 : s1.lines) {
			for (Point2D.Double point2 : s2.points) {
				res = Math.min(res, line1.ptSegDist(point2));
			}
		}
		
		
		for (Line2D.Double line2 : s2.lines) {
			for (Point2D.Double point1 : s1.points) {
				res = Math.min(res, line2.ptSegDist(point1));
			}
		}
		
		for (Point2D.Double point2 : s2.points) {
			for (Point2D.Double point1 : s1.points) {
				//System.out.println(point2.distance(point1));
				res = Math.min(res, point2.distance(point1));
			}
		}
		return res;
	}
	
	/* -----------Dijkstra---------- */
	public class Dijkstra {
		final static int INF = 1000000000;
		
		class State implements Comparable<State> {
			int n;
			
			State(int n) {
				this.n = n;
			}

			public int compareTo(State s) {
				double c1 = res.minCost[n], c2 = res.minCost[s.n];
				if (c1 < c2) return -1;
				else if (c1 > c2) return 1;
				else return 0;
			}
		}
		
		DijkstraResult res;
		double[][] edge;
		
		Dijkstra(double[][] edge) {
			this.edge = edge;
		}
		
		DijkstraResult doit(int start) {
			int n = edge.length;
			res = new DijkstraResult(n);
			Arrays.fill(res.minCost, Dijkstra.INF);
			
			PriorityQueue<State> pq = new PriorityQueue<State>();
			pq.add(new State(start));
			res.minCost[start] = 0;
			res.path[start] = start;
			
			while (!pq.isEmpty()) {
				State s = pq.poll();
				for (int i = 0; i < n; i++) {
					if (res.minCost[i] > res.minCost[s.n] + edge[s.n][i]) {
						res.minCost[i] = res.minCost[s.n] + edge[s.n][i];
						res.path[i] = s.n;
						pq.add(new State(i));
					}
				}
			}
			
			return res;
		}
	}

	/**
	 * it contains minCost and path from start node to each nodes.
	 * @author hiro116s
	 *
	 */
	class DijkstraResult {
		double[] minCost;
		int[] path;
		
		DijkstraResult(int n) {
			minCost = new double[n];
			path = new int[n];
		}
	}
	
	/*-------------end--------------*/
	
	public void run() {
		while (true) {
			int n = in.nextInt(), m = in.nextInt(), l = in.nextInt();
			if (n == 0) break;
			Star[] stars = new Star[n];
			for (int i = 0; i < n; i++) {
				int x = in.nextInt(), y = in.nextInt(), a = in.nextInt(), r = in.nextInt();
				stars[i] = new Star(x, y, a, r);
			}
			
			double[][] edge = new double[n][n];
			for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
				if (i == j) continue;
				edge[i][j] = culcDist(stars[i], stars[j]);
			}
			
			for (int i = 0; i < edge.length; i++) {
				//System.out.println(stars[i].toString());
				//System.out.println(Arrays.toString(edge[i]));
			}
			
			System.out.println(new Dijkstra(edge).doit(m-1).minCost[l-1]);
		}
		out.close();
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}