Codeforces Round #308 Div2 D: Vanya and Triangles

問題

codeforces.com

解法

全ての組み合わせを列挙すると通りあるため、間に合わない（と思われていたがC++なら間に合う）。

3点が同一直線上にあるパターンと、3点のうち2点以上が重なっているパターンを除けば良い。

• まず、点iに注目し、他の点の座標をiを原点とした座標に直す。この際、iと重なっている点は除外する。
• iおよびiと重なっている点を除いた点の数をMとすると、考えうる組み合わせはである。
• iを原点とした時、点jと点kについて、x軸とのなす角が同じならば、i, j, kは同一直線上にあることになる。
• つまりx軸となす角でソートしてグループごとに除いてやればよい。

上記操作を全てのiについて行う。角度を小数で出してしまったので誤差死する。

コード

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

public class Main {
	private final double EPS = 1e-10;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] x = new int[N];
		int[] y = new int[N];
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
		}
		sc.close();

		long sum = 0;
		for (int i = 0; i < N; i++) {
			// 点iが三角形に含まれる場合を考える

			// ベクトルを列挙
			ArrayList<Double> rads = new ArrayList<>();
			for (int j = i + 1; j < N; j++) {
				if (j != i) {
					int vx = x[j] - x[i];
					int vy = y[j] - y[i];
					if (vx != 0 || vy != 0) {
						//vxとvyがともに0になるパターンを除外しておく
						double rad = Math.atan2(vy, vx);
						if (rad <= 0) {
							rad += Math.PI;
						}
						rads.add(rad);
					}
				}
			}

			int M = rads.size();
			long all = (long) M * (M - 1) / 2;

			Collections.sort(rads);

			int j = 0;
			while (j < rads.size()) {
				int k = j;
				while (k < rads.size() && Math.abs(rads.get(j) - rads.get(k)) < EPS) {
					k++;
				}
				all -= (long) (k - j) * (k - j - 1) / 2;
				j = k;
			}
			sum += all;
		}
		System.out.println(sum);
	}

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

}