UVA – 1096 – The Islands   Leave a comment


import java.io.*;
import java.util.*;

public class UVa1096 {
	static Double[][] dp;
	static int p1;
	static int p2;
	static Point[] inp;
	static byte[][] dec;

	static class Point {
		int x, y;

		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		double distance(Point p) {
			return Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
		}

	}

	public static double go(int i, int j) {
		int ind = Math.max(i, j) + 1;
		if (dp[i][j] != null)
			return dp[i][j];
		if (ind == inp.length - 1)
			return dp[i][j] = inp[i].distance(inp[ind])
					+ inp[j].distance(inp[ind]);
		if (ind == p1) {
			dec[i][j] = -1;
			return dp[i][j] = inp[i].distance(inp[ind]) + go(p1, j);
		}
		if (ind == p2) {
			dec[i][j] = 1;
			return dp[i][j] = inp[j].distance(inp[ind]) + go(i, p2);
		}

		double d0 = inp[i].distance(inp[ind]) + go(ind, j);

		double d1 = inp[j].distance(inp[ind]) + go(i, ind);

		if (d0 < d1) {
			dec[i][j] = -1;
			return dp[i][j] = d0;
		} else {
			dec[i][j] = 1;
			return dp[i][j] = d1;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int cc = 1;
		while (true) {
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			int n = Integer.parseInt(strtok.nextToken());
			p1 = Integer.parseInt(strtok.nextToken());
			p2 = Integer.parseInt(strtok.nextToken());
			if (n == 0 && p1 == 0 && p2 == 0)
				break;
			dp = new Double[n][n];
			inp = new Point[n];
			for (int i = 0; i < n; i++) {
				strtok = new StringTokenizer(in.readLine());
				inp[i] = new Point(Integer.parseInt(strtok.nextToken()),
						Integer.parseInt(strtok.nextToken()));
			}
			dec = new byte[n][n];
			go(0, 0);
			LinkedList<Integer> r0 = new LinkedList<Integer>();
			r0.add(0);
			Stack<Integer> r1 = new Stack<Integer>();
			r1.push(0);
			int i = 0, j = 0, ind = 1;
			while (ind != n - 1) {
				if (dec[i][j] == 1) {
					r1.push(ind);
					j = ind;
					ind++;
				} else {
					r0.add(ind);
					i = ind;
					ind++;
				}
			}
			r0.add(n - 1);
			while (!r1.isEmpty())
				r0.add(r1.pop());
			int[] res = new int[r0.size()];
			int top = 0;
			for (int x : r0)
				res[top++] = x;
			double tot = 0;
			for (int a = 1; a < res.length; a++)
				tot += inp[res[a - 1]].distance(inp[res[a]]);

			StringBuilder out = new StringBuilder("");
			if (res[1] == 1) {
				out.append(res[0]);
				for (int k = 1; k < res.length; k++)
					out.append(" " + res[k]);
			} else {
				out.append(res[res.length - 1]);
				for (int k = res.length - 2; k >= 0; k--)
					out.append(" " + res[k]);
			}

			System.out.printf("Case %d: %.2f\n", cc++, tot);
			System.out.println(out);
		}
	}
}

Advertisements

Posted March 28, 2012 by epicrado in ACM-ICPC, Dynamic programming, UVA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: