Good Bye 2017 C New Year and Curling

問題

codeforces.com

半径rの円の中心のx座標がN個与えられる。
i = 0,1,2,3...N-1の順に円はy=10^100からy = 0に向かって進む。
他の円に接した時、y = 0に円が接した時に円は止まる。
最終的なN個の円のy座標を求める。

考察

i番目の円aをy=0に向かって進める際に、既に止まっているj番目(j < i)の円bを考える。

abs(x[i] - x[j])がr * 2(円aの半径+円bの半径)より大きい場合はその円同士は接することはない。
abs(x[i] - x[j])がr * 2以下の場合は接するので、円aと円bの距離は必ずr * 2になる。
後は三平方の定理からsqrt( (r * 2) * (r * 2) - abs(x[i] - x[j]) * abs(x[i] - x[j]) )が円aと円bのy座標の距離となる。

y[j] + (円aと円bのy座標の距離)の最大値が円aの最終的なy座標となる。

ソースコード

戒め
これは色々良くないコードで
y座標が大きいものから取って、円が止まるy座標を二分探索してる

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int N,r;
    int[] x;
    ArrayList<Point> points;

    private class Point implements Comparable<Point>{
        double y,x;

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

        public int compareTo(Point point) {
            return Double.compare(point.y,this.y);
        }
    }

    private double dis(Point p,double y,double x) {
        return (p.y - y) * (p.y - y) + (p.x - x) * (p.x - x);
    }

    private boolean isHit(double y,double x) {
        for(Point p : points) {
            if (dis(p,y,x)  <= (r * 2) * (r * 2)) {
                return true;
            }
        }

        return false;
    }

    private double getY(PriorityQueue<Point> q,double x) {

        double lowY = r;

        while(q.size() > 0) {
            Point p = q.poll();
            if (isHit(p.y,x)) {
                lowY = Math.max(lowY,p.y);
            }
        }

        double low = lowY;
        double high = 10000000;

        for(int j = 0;j < 100;j++) {
            double mid = (high + low) / 2;

            if (isHit(mid,x)) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return high;
    }

    private void solve() {
        N = nextInt();
        r = nextInt();

        x = new int[N];
        for(int i = 0;i < N;i++) {
            x[i] = nextInt();
        }

        PriorityQueue<Point> pq = new PriorityQueue<>();
        points = new ArrayList<>();

        for(int i = 0;i < N;i++) {
            PriorityQueue<Point> tmp = new PriorityQueue<>();
            tmp.addAll(pq);

            double minY = getY(tmp,x[i]);

            pq.add(new Point(minY,x[i]));
            points.add(new Point(minY,x[i]));
        }

        for(int i = 0;i < points.size();i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(String.format("%.09f",points.get(i).y));
        }

        out.println();
    }

    public static void main(String[] args) {
        out.flush();
        new C().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

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

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

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

これは想定解で解き直したやつ(スッキリ)

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int N,r;
    int[] x;
    double[] y;

    private void solve() {
        N = nextInt();
        r = nextInt();

        x = new int[N];
        y = new double[N];
        for(int i = 0;i < N;i++) {
            x[i] = nextInt();
        }

        for(int i = 0;i < N;i++) {
            double maxY = r;

            for(int j = 0;j < i;j++) {
                int distanceX = Math.abs(x[i] - x[j]);
                if (distanceX <= r * 2) {
                    maxY = Math.max(maxY,y[j] + Math.sqrt((r * 2) * (r * 2) - distanceX * distanceX));
                }
            }
            y[i] = maxY;
        }

        for(int i = 0;i < N;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(String.format("%.09f",y[i]));
        }

        out.println();
    }

    public static void main(String[] args) {
        out.flush();
        new C().solve();
        out.close();
    }
}