GCJ 2012 Round2Aerobics

Aerobics.java

package com.polysfactory.gcj2013;

import java.util.Arrays;
import java.util.Scanner;

public class Aerobics {

    static class Entry implements Comparable<Entry> {
        int r;
        int index;

        public Entry(int r, int index) {
            this.r = r;
            this.index = index;
        }

        @Override
        public int compareTo(Entry o) {
            return o.r - this.r;
        }
    }

    static class Point {
        double x;
        double y;

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

        public String toString() {
            return String.format(" %.5f %.5f", this.x, this.y);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int tt = 0; tt < T; tt++) {
            int n = scanner.nextInt();
            int w = scanner.nextInt();
            int l = scanner.nextInt();
            Entry entries[] = new Entry[n];
            for (int i = 0; i < n; i++) {
                entries[i] = new Entry(scanner.nextInt(), i);
            }
            Arrays.sort(entries);
            Point[] points = solve(n, w, l, entries);
            String ans = "";
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (entries[j].index == i) {
                        ans += points[j].toString();
                    }
                }
            }

            System.out.println("Case #" + (tt + 1) + ":" + ans);
        }
    }

    private static double EPS = 0.00001;

    private static Point[] solve(int n, int w, int l, Entry[] entries) {
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            // put entires[i]
            int r = entries[i].r;
            while (true) {
                // randomly pick up (x,y)
                double x = Math.random() * w;
                double y = Math.random() * l;

                // check x,y
                boolean ok = true;
                for (int j = 0; j < i; j++) {
                    Point p = points[j];
                    double dx = x - p.x;
                    double dy = y - p.y;
                    double dist = Math.sqrt(dx * dx + dy * dy);
                    if (dist - EPS < entries[j].r + r) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    points[i] = new Point(x, y);
                    break;
                }
            }
        }
        return points;
    }
}

SwingingWild.java

package com.polysfactory.gcj2013;

import java.util.Arrays;
import java.util.Scanner;

public class SwingingWild {
    static class Vine implements Comparable<Vine> {
        int d;
        int l;

        @Override
        public int compareTo(Vine o) {
            return this.d - o.d;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int tt = 0; tt < T; tt++) {
            int n = scanner.nextInt();
            int[] dp = new int[n];
            Vine[] vines = new Vine[n];
            for (int i = 0; i < n; i++) {
                Vine vine = new Vine();
                vine.d = scanner.nextInt();
                vine.l = scanner.nextInt();
                vines[i] = vine;
            }
            int d = scanner.nextInt();

            Arrays.sort(vines);
            dp[0] = vines[0].d;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (dp[j] > 0) {
                        int maxDist = vines[j].d + dp[j];
                        if (maxDist >= vines[i].d) {
                            dp[i] = Math.max(dp[i], Math.min(vines[i].l, vines[i].d - vines[j].d));
                        }
                    }
                }
            }
            boolean reachable = false;
            for (int i = 0; i < n; i++) {
                if (dp[i] > 0 && vines[i].d + dp[i] >= d) {
                    reachable = true;
                    break;
                }
            }
            if (reachable) {
                System.out.println("Case #" + (tt + 1) + ": YES");
            } else {
                System.out.println("Case #" + (tt + 1) + ": NO");
            }
        }
    }
}