提出 #64680756

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (long long i = 0; i < (n); i++)

// #define DEBUG

const int MAX_N = 15;

long long X[MAX_N], Y[MAX_N];
long long N, K;
long long ans = LONG_LONG_MAX;

// K < N なのでNで初期化しちゃう
vector<int> points[MAX_N];

long long findMaxDist()
{
    long long maxDist = 0;
    // 最大距離を求める処理
    for (int id = 0; id < K; id++)
    {
        auto group = points[id];

        if (group.size() < 1)
        {
            // 1点の場合、距離はない
            continue;
        }

        // 距離を求める
        for (int i = 0; i < group.size() - 1; i++)
        {
            for (int j = i + 1; j < group.size(); j++)
            {
                int p1 = group[i];
                int p2 = group[j];
                long long dx = X[p1] - X[p2];
                long long dy = Y[p1] - Y[p2];
                long long dist = dx * dx + dy * dy;
                maxDist = max(dist, maxDist);
            }
        }
    }
    return maxDist;
}

void dfs(
    int n,     // 点の番号
    int k,     // 今使っている箱の数
    int target // 入れたい箱の番号
)
{
    // 存在しない箱なので終了
    if (K <= target)
    {
        return;
    }

    // K - k 未使用の箱
    // N - n + 1　残りのボール数
    // どんな入れ方でも条件を満たさない
    if (N - n + 1 < K - k)
    {
        return;
    }

    // 箱iに点を追加
    points[target].push_back(n);

    if (n + 1 == N)
    {
        if (k == K)
        {
            long long maxDist = findMaxDist();
            ans = min(ans, maxDist);
        }
    }
    else
    {
        // 箱の数は変えずに、次の点を今までの箱に追加
        for (int j = 0; j <= k; j++)
        {
            dfs(n + 1, k, j);
        }

        // 新しい箱を用意して投入
        dfs(n + 1, k + 1, k);
    }

    // 　上の階に戻るので、入れた値を削除
    auto it = lower_bound(
        points[target].begin(),
        points[target].end(),
        n);

    points[target].erase(it);
}

int main()
{
#ifdef DEBUG
    freopen("input/in.txt", "r", stdin);
#endif

    cin >> N >> K;
    rep(i, N)
    {
        cin >> X[i] >> Y[i];
    }

    // 0の点を0の箱に追加
    dfs(0, 1, 0);

    cout << ans << endl;

    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘long long int findMaxDist()’:
Main.cpp:32:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   32 |         for (int i = 0; i < group.size() - 1; i++)
      |                         ~~^~~~~~~~~~~~~~~~~~
Main.cpp:34:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   34 |             for (int j = i + 1; j < group.size(); j++)
      |                                 ~~^~~~~~~~~~~~~~

ジャッジ結果