SRM 652 Div. 2 Hard: NoRightTurnDiv2

問題

TopCoder Statistics - Problem Statement

解法

点0から始めて、曲がり角が最も大きくなるように貪欲に点を取っていくと上手くいく。

コード

public class NoRightTurnDiv2 {
	double[] direction(int[] X, int[] Y, int from, int to) {
		// fromからtoへの単位ベクトルを返す
		double dx = X[to] - X[from];
		double dy = Y[to] - Y[from];
		return new double[] { dx / Math.sqrt(dx * dx + dy * dy), dy / Math.sqrt(dx * dx + dy * dy) };
	}

	double product(double[] a, double[] b) {
		// ベクトル内積を返す
		return a[0] * b[0] + a[1] * b[1];
	}

	public int[] findPath(int[] x, int[] y) {
		int start = 0;
		int N = x.length;

		// x座標のもっとも大きい点を始点にする
		for (int i = 1; i < N; i++) {
			if (x[start] < x[i])
				start = i;
		}

		int[] ans = new int[N];
		ans[0] = start;

		boolean[] used = new boolean[N];
		used[start] = true;

		// Y軸の正の向きの単位ベクトル
		double[] prevDir = new double[2];
		prevDir[0] = 0.0;
		prevDir[1] = 1.0;

		for (int i = 1; i < N; i++) {
			int from = ans[i - 1];
			double max = -2;
			int next = -1;

			for (int to = 0; to < N; to++) {
				if (!used[to]) {
					// 前のベクトルに対して最も内積が大きくなるように次の点を探す
					// そうすると、曲がり角を最大にすることが出来る
					double[] toDir = direction(x, y, from, to);
					double pro = product(prevDir, toDir);
					if (max < pro) {
						max = pro;
						next = to;
					}
				}
			}
			prevDir = direction(x, y, from, next);
			ans[i] = next;
			used[next] = true;
		}
		return ans;
	}
}