AtCoder Regular Contest 042 B: アリの高橋くん

問題

arc042.contest.atcoder.jp

解法

幾何ライブラリ貼るだけ。

コード

import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int sx = scanner.nextInt();
		int sy = scanner.nextInt();
		Vector2D start = new Vector2D(sx, sy);

		int N = scanner.nextInt();
		Vector2D[] vector2ds = new Vector2D[N];
		for (int i = 0; i < N; i++) {
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			vector2ds[i] = new Vector2D(x, y);
		}

		double ans = 100000.0;
		for (int i = 0; i < N - 1; i++) {
			double dist = distanceDotAndLine(start, vector2ds[i],
					vector2ds[i + 1]);
			ans = Math.min(dist, ans);
		}
		double dist = distanceDotAndLine(start, vector2ds[N - 1], vector2ds[0]);
		ans = Math.min(dist, ans);
		System.out.println(ans);

	}

	// 点Pと線(AB)の距離
	private double distanceDotAndLine(Vector2D P, Vector2D A, Vector2D B) {
		Vector2D AB = new Vector2D(B.x - A.x, B.y - A.y);
		Vector2D AP = new Vector2D(P.x - A.x, P.y - A.y);

		// ベクトルAB、APの外積の絶対値が平行四辺形Dの面積になる
		double D = Math.abs(crossVector(AB, AP));

		double L = distanceVertex(A, B); // AB間の距離

		double H = D / L;
		return H;
	}

	// 点間距離
	private double distanceVertex(Vector2D p1, Vector2D p2) {
		double dx = p1.x - p2.x;
		double dy = p1.y - p2.y;
		return Math.sqrt(dx * dx + dy * dy);
	}

	// ベクトル外積
	private double crossVector(Vector2D vl, Vector2D vr) {
		return vl.x * vr.y - vl.y * vr.x;
	}

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

}

class Vector2D {
	double x;
	double y;

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