けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

diverta 2019_2 B - Picking Up (緑色, 300 点)

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。
そして  N = 1 のケースが結構厄介 ^^;

問題へのリンク

問題概要

二次元平面上に  N 点がある。最初に整数  p, q を自分で決める。そして、 N 個の点を好きな順序で順に辿っていく。このとき、

  • 最初の点では +1
  • その後移動するたびに、移動ベクトルが  (p, q) のときは +0
  • そうでないときは +1

したものがペナルティとなる。ペナルティの最小値を求めよ。

制約

  •  1 \le N \le 50

考えたこと

まず  p, q の選び方が途方もなく多く見えるがそんなことはなく、

  • ある  i \neq j についての  (x_j - x_i, y_j - y_i)

についてのみ試せば十分である。なぜなら、どの 2 点をとってもその差ベクトルになってないような  p, q を使ったらペナルティは  N-1 になる。これより小さくはできない。なので、上記の場合だけ試せばよい。この時点で  O(N^{2}) 通り。

さて、 p, q を決めたらあとは、実際に  N 点を上手く並べることで、なるべく  (p, q) なジャンプが多くなるようにしたい。再びすべての  i \neq j に対して調べることで、 (p, q) なジャンプが何個あるのかを求めればよい。

ただし、 N = 1 の場合に要注意!!!!!

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> x, y;

int solve() {
    if (N == 1) return 1;

    int res = N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            long long dx = x[j] - x[i], dy = y[j] - y[i];

            int sub = 0;
            for (int i2 = 0; i2 < N; ++i2) {
                for (int j2 = 0; j2 < N; ++j2) {
                    if (j2 == i2) continue;
                    if (dx == x[j2] - x[i2] && dy == y[j2] - y[i2]) ++sub;
                }
            }
            res = min(res, N - sub);
        }
    }
    return res;
}

int main() {
    cin >> N;
    x.resize(N); y.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    cout << solve() << endl;
}