Picking Up [diverta 2019 Programming Contest 2 B]

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b

前提知識

• UnionFind

解説

https://atcoder.jp/contests/diverta2019-2/submissions/5943792

なにか全探索対象を探す。
どこを全探索しようかなと色々考える。
1つ目を全探索すると、自由度が高すぎるので、Nの大きさとも相談して、2つ目まで全探索してみる。
p,qが固定になりそう。
p,qが固定になっていると、最適に計算しやすいのでは？
p,qを固定にしてみる。
　
p,qを固定すると、コスト0のボール間に辺を貼ったときに、パスの集合となるグラフができあがる。
パスになっている連結成分はすべてコスト1で回収可能であるため、
この問題はコスト0のボール間に辺を貼ったときに、連結成分の個数を答える問題となった。
これはUnionFindを使って計算可能である。
　
この計算は十分に間に合う。

int N, X[50], Y[50];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> X[i] >> Y[i];

	if (N == 1) {
		cout << 1 << endl;
		return;
	}
	
	int ans = inf;
	rep(a, 0, N) rep(b, a + 1, N) {
		int p = X[a] - X[b];
		int q = Y[a] - Y[b];

		if (p == 0 and q == 0) continue;

		UnionFind uf(N);
		rep(i, 0, N) rep(j, 0, N) if (X[i] + p == X[j] and Y[i] + q == Y[j]) uf(i, j);

		int cst = 0;
		rep(i, 0, N) if (uf[i] == i) cst++;
		chmin(ans, cst);
	}

	cout << ans << endl;
}