2010年 夏合宿4日目 Problem E : Psychic Accelerator [Licence: NYSL Version 0.9982]

Guide.java

import java.util.*;
import static java.lang.Math.*;

public class Guide {
  public static void main(String... args) {
		new Guide().run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a = sc.nextInt();

		P[][] p = new P[2][N];
		for (int i = 0; i < N; i++)
			for (int k = 0; k < 2; k++)
				p[k][i] = new P(Double.parseDouble(sc.next()), Double.parseDouble(sc.next()));

		double[] l = new double[N];
		for (int i = 0; i < N; i++)
			l[i] = p[0][i].dist(p[1][i]);

		double[] v2 = new double[N + 1]; // limit of velocity^2
		double[] c = new double[N + 1];
		for (int i = 1; i < N; i++) {
			P ctr = center(p[0][i - 1], p[1][i - 1], p[0][i], p[1][i]);

			double r = p[0][i].dist(ctr);
			double t = p[0][i].sub(ctr).arg(p[1][i - 1].sub(ctr));
			if (p[1][i - 1].sub(p[0][i - 1]).cross(p[0][i].sub(p[1][i - 1])) < 0)
				t *= -1;
			if (t < 0)
				t += 2 * PI;
			v2[i] = a * r;
			c[i] = r * t;
		}

		// l.o.v. from DST
		for (int i = N - 1; i > 0; i--)
			v2[i] = min(v2[i], v2[i + 1] + 2 * a * l[i]);
		// l.o.v. from SRC
		for (int i = 1; i < N; i++)
			v2[i] = min(v2[i], v2[i - 1] + 2 * a * l[i - 1]);

		double[] v = new double[N + 1];
		for (int i = 1; i < N; i++)
			v[i] = sqrt(v2[i]);

		double time = 0;
		for (int i = 1; i < N; i++)
			time += c[i] / v[i];
		for (int i = 0; i < N; i++) {
			double vmax = sqrt(.5 * (v2[i] + v2[i + 1]) + a * l[i]);
			time += (2 * vmax - v[i] - v[i + 1]) / a;
		}
		System.out.println(time);
	}

	class P {
		final double x, y;

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

		P add(P p) {
			return new P(x + p.x, y + p.y);
		}

		P sub(P p) {
			return new P(x - p.x, y - p.y);
		}

		double dot(P p) {
			return x * p.x + y * p.y;
		}

		double cross(P p) {
			return x * p.y - y * p.x;
		}

		double norm() {
			return hypot(x, y);
		}

		double dist(P p) {
			return sub(p).norm();
		}

		double arg() {
			return atan2(y, x);
		}

		double arg(P p) {
			return new P(dot(p), -cross(p)).arg();
		}

		@Override
		public String toString() {
			return String.format("(%.2f, %.2f)", x, y);
		}
	}

	static final double EPS = 1e-8;

	P center(P p1, P p2, P p3, P p4) {
		P a1 = p1.sub(p2);
		P a2 = p3.sub(p4);
		P v1 = new P(a1.x, a2.x);
		P v2 = new P(a1.y, a2.y);
		P v = new P(a1.dot(p2), a2.dot(p3));
		double det = v1.cross(v2);
		if (abs(det) < EPS) {
			P p = p2.add(p3);
			return new P(.5 * p.x, .5 * p.y);
		}
		return new P(v.cross(v2) / det, v1.cross(v) / det); // Cramer
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}