読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 521 Div1 Medium: RangeSquaredSubsets

コード

import java.util.Arrays;
import java.util.HashSet;

public class RangeSquaredSubsets {

	public long countSubsets(int nlow, int nhigh, int[] x, int[] y) {
		int N = x.length;
		int[] sX = Arrays.copyOf(x, N);
		int[] sY = Arrays.copyOf(y, N);
		Arrays.sort(sX);
		Arrays.sort(sY);

		HashSet<Long> bitSet = new HashSet<>();
		for (int xl = 0; xl < N; xl++) {
			for (int xr = xl; xr < N; xr++) {
				for (int yl = 0; yl < N; yl++) {
					for (int yr = yl; yr < N; yr++) {

						// sX[xr], sX[xl], sY[yr], sY[yl]を含む正方形を作る
						int dx = sX[xr] - sX[xl];
						int dy = sY[yr] - sY[yl];
						int length = Math.max(Math.max(dx, dy), nlow);
						if (length > nhigh) {
							continue;
						}

						// 外側の辺を含んでいる場合はスルー
						if (0 < xl && xr < N - 1
								&& sX[xr + 1] - sX[xl - 1] <= length) {
							continue;
						}
						if (0 < yl && yr < N - 1
								&& sY[yr + 1] - sY[yl - 1] <= length) {
							continue;
						}

						long bit = 0;
						for (int i = 0; i < N; i++) {
							if (x[i] < sX[xl] || sX[xr] < x[i]) {
								continue;
							}
							if (y[i] < sY[yl] || sY[yr] < y[i]) {
								continue;
							}

							// 正方形の内側に含まれていればビットに加える
							bit |= (long) 1 << i;
						}

						if (bit > 0) {
							bitSet.add(bit);
						}
					}
				}
			}
		}

		return bitSet.size();
	}
}