結果

問題 No.5020 Averaging
ユーザー SnowBeenDiding
提出日時 2025-04-11 15:37:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 1,000 ms
コード長 3,871 bytes
コンパイル時間 5,954 ms
コンパイル使用メモリ 333,228 KB
実行使用メモリ 7,848 KB
スコア 22,598,265
最終ジャッジ日時 2025-04-11 15:38:00
合計ジャッジ時間 12,710 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

ll tar = 5e17;

int n;
vector<ll> a, b;
vector<int> u, v;

ll cross(pair<ll, ll> a, pair<ll, ll> b) {
    __int128_t x = a.first * b.second - a.second * b.first;
    if (x > 0)
        return 1;
    if (x < 0)
        return -1;
    return 0;
}

pair<ll, ll> vec(pair<ll, ll> a, pair<ll, ll> b) {
    return {b.first - a.first, b.second - a.second};
}

bool inside(pair<ll, ll> p, pair<ll, ll> q, pair<ll, ll> r, pair<ll, ll> x) {
    auto v1 = cross(vec(p, q), vec(p, x));
    auto v2 = cross(vec(q, r), vec(q, x));
    auto v3 = cross(vec(r, p), vec(r, x));
    bool ret =
        (v1 >= 0 && v2 >= 0 && v3 >= 0) || (v1 <= 0 && v2 <= 0 && v3 <= 0);
    return ret;
}

ll solve(int i0, int i1, int i2, int i3) {
    u.clear();
    v.clear();
    vector<ll> x(n), y(n);
    rep(i, 0, n) {
        x[i] = a[i] - tar;
        y[i] = b[i] - tar;
    }
    auto f = [&](int i, int j) {
        u.push_back(i);
        v.push_back(j);
        ll mx = (x[i] + x[j]) / 2;
        ll my = (y[i] + y[j]) / 2;
        x[i] = x[j] = mx;
        y[i] = y[j] = my;
    };
    f(i0, i1);
    f(i2, i3);
    while (u.size() < 50) {
        vector<int> ids = {0, i0, i1, i2, i3};
        map<pair<ll, ll>, vector<int>> groups;
        for (int i : ids) {
            groups[{x[i], y[i]}].push_back(i);
        }

        // 座標が一致している点をグループ化
        vector<vector<int>> clusters;
        for (auto &[_, vec] : groups) {
            clusters.push_back(vec);
        }

        // グループ数が3つであることが前提
        if (clusters.size() != 3) {
            cerr << "グループ数が3つではありません" << endl;
            break;
        }

        // サイズ1のグループが X（孤立点）、サイズ2のグループが Y と Z
        int X, Y1, Y2, Z1, Z2;
        if (clusters[0].size() == 1) {
            X = clusters[0][0];
            Y1 = clusters[1][0], Y2 = clusters[1][1];
            Z1 = clusters[2][0], Z2 = clusters[2][1];
        } else if (clusters[1].size() == 1) {
            X = clusters[1][0];
            Y1 = clusters[0][0], Y2 = clusters[0][1];
            Z1 = clusters[2][0], Z2 = clusters[2][1];
        } else {
            X = clusters[2][0];
            Y1 = clusters[0][0], Y2 = clusters[0][1];
            Z1 = clusters[1][0], Z2 = clusters[1][1];
        }

        // 三角形 X, Y1, Z1 の中に原点があるかをチェック
        if (!inside({x[X], y[X]}, {x[Y1], y[Y1]}, {x[Z1], y[Z1]}, {0, 0}))
            break;

        // XとY1の中点をPとし、P, Z1, Y1 の三角形に原点があるかをチェック
        ll px = (x[X] + x[Y1]) / 2, py = (y[X] + y[Y1]) / 2;
        if (inside({px, py}, {x[Z1], y[Z1]}, {x[Y1], y[Y1]}, {0, 0})) {
            f(X, Y1);
            continue;
        }

        // XとZ1の中点をPとし、P, Y1, Z1 の三角形に原点があるかをチェック
        px = (x[X] + x[Z1]) / 2, py = (y[X] + y[Z1]) / 2;
        if (inside({px, py}, {x[Y1], y[Y1]}, {x[Z1], y[Z1]}, {0, 0})) {
            f(X, Z1);
            continue;
        }

        break;
    }

    return max(abs(x[0]), abs(y[0]));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    a.resize(n);
    b.resize(n);
    rep(i, 0, n) cin >> a[i] >> b[i];
    ll penalty = LLONG_MAX;
    vector<int> ans_u, ans_v;
    rep(i, 1, n) rep(j, i + 1, n) rep(k, j + 1, n) rep(l, k + 1, n) {
        ll pe = solve(i, j, k, l);
        if (pe < penalty) {
            penalty = pe;
            ans_u = u;
            ans_v = v;
        }
    }
    cout << ans_u.size() << endl;
    rep(i, 0, ans_u.size()) cout << ans_u[i] + 1 << " " << ans_v[i] + 1 << endl;
}
0