Codeforces Round #299 Div2 E: Tavas and Pashmaks（凸包）

問題

codeforces.com

解法

mayokoex.hatenablog.com

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	private final int MAX = 10001;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		P[] ps = new P[N];
		int[] s = new int[N];
		int[] r = new int[N];
		int[] maxr = new int[MAX];
		for (int i = 0; i < ps.length; i++) {
			s[i] = sc.nextInt();
			r[i] = sc.nextInt();
			ps[i] = new P(1.0 / s[i], 1.0 / r[i]);
			maxr[s[i]] = Math.max(maxr[s[i]], r[i]);
		}

		ArrayList<Integer>[] maxrIDs = new ArrayList[MAX];
		for (int i = 0; i < MAX; i++) {
			maxrIDs[i] = new ArrayList<>();
		}

		for (int i = 0; i < N; i++) {
			if (r[i] == maxr[s[i]]) {
				maxrIDs[s[i]].add(i + 1);
			}
		}

		P[] qs = convexHull(ps);
		Arrays.sort(qs);
		ArrayList<Integer> ans = new ArrayList<>();
		int y = -1;
		for (int i = MAX - 1; i >= 0; i--) {
			if (maxrIDs[i].size() == 0) {
				continue;
			}
			if (y != -1 && maxr[y] >= maxr[i]) {
				continue;
			}
			P p = new P(1.0 / i, 1.0 / maxr[i]);
			if (Arrays.binarySearch(qs, p) >= 0) {
				for (Integer e : maxrIDs[i]) {
					ans.add(e);
				}
			}
			y = i;
		}
		Collections.sort(ans);
		for (Integer integer : ans) {
			System.out.print(integer + " ");
		}
		System.out.println();
	}

	private P[] convexHull(P[] ps) {
		double EPS = 1e-30;
		int n = ps.length;
		int k = 0;
		Arrays.sort(ps);
		P[] qs = new P[n * 2];
		for (int i = 0; i < n; i++) {
			while (k > 1 && (qs[k - 1].sub(qs[k - 2])).det(ps[i].sub(qs[k - 1])) < EPS) {
				k--;
			}
			qs[k] = ps[i];
			k++;
		}

		P[] res = new P[k];
		System.arraycopy(qs, 0, res, 0, k);
		return res;
		// int t = k;
		// for (int i = n - 2; i >= 0; i--) {
		// while (k > t && (qs[k - 1].sub(qs[k - 2])).det(ps[i].sub(qs[k - 1]))
		// < EPS) {
		// k--;
		// }
		// qs[k] = ps[i];
		// k++;
		// }
		// P[] res = new P[k - 1];
		// System.arraycopy(qs, 0, res, 0, k - 1);
		// return res;
	}

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

}

// 2次元座標
class P implements Comparable<P> {
	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);
	}

	P mul(double m) {
		return new P(x * m, y * m);
	}

	P div(double d) {
		return new P(x / d, y / d);
	}

	double abs() {
		return Math.sqrt(abs2());
	}

	double abs2() {
		return x * x + y * y;
	}

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

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

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

	double ang(P p) {
		return Math.atan2(det(p), dot(p));
	}

	P rot90() {
		return new P(y, -x);
	}

	P rot(double d) {
		return new P(Math.cos(d) * x - Math.sin(d) * y, Math.sin(d) * x + Math.cos(d) * y);
	}

	public int compareTo(P p) {
		return Double.compare(x, p.x) * 2 + Double.compare(y, p.y);
	}
}