結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー wanui
提出日時 2022-07-30 14:43:26
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,976 bytes
コンパイル時間 3,550 ms
実行使用メモリ 3,548 KB
スコア 7,045,407
最終ジャッジ日時 2022-07-30 14:43:33
合計ジャッジ時間 3,432 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on

// K-meansやりたい！

struct point {
    double i;
    double j;
};

const int N = 100;
const int M = 8;
const int ALPHA = 5;

vector<point> planets(N);
double distance(point a, point b) {
    return sqrt((a.i - b.i) * (a.i - b.i) + (a.j - b.j) * (a.j - b.j));
}
void solve() {
    // k-means
    // 初期値は固定(TODO)
    vector<point> stations = {
        {166, 166},
        {333, 500},
        {166, 833},
        {500, 666},
        {833, 833},
        {666, 500},
        {833, 166},
        {500, 333},
    };
    assert(stations.size() == M);

    vector<int> pre_assign(N, -1);
    for (int iter = 0; iter < 10000; iter++) {
        vector<int> assign(N);
        for (int pid = 0; pid < N; pid++) {
            auto pl = planets[pid];
            double mindist = 1e18;
            int minstation = -1;
            for (int sid = 0; sid < M; sid++) {
                auto st = stations[sid];
                double d = distance(pl, st);
                if (mindist > d) {
                    mindist = d;
                    minstation = sid;
                }
            }
            assign[pid] = minstation;
        }
        if (pre_assign == assign) {
            break;
        }
        vector<point> sums(M, {0, 0});
        vector<int> counts(M);
        for (int pid = 0; pid < N; pid++) {
            auto pl = planets[pid];
            auto sid = assign[pid];
            sums[sid].i += pl.i;
            sums[sid].j += pl.j;
            counts[sid]++;
        }
        for (int sid = 0; sid < M; sid++) {
            int cnt = counts[sid];
            auto su = sums[sid];
            if (cnt == 0) {
                // TODO 初期値の選び方によってこれを起こさないことはできるが...
                // stationの位置に変更なし
                continue;
            }

            stations[sid] = {su.i / cnt, su.j / cnt};
        }
        pre_assign = assign;
    }
    // クラスタの移動は適当に決め打ち。 // TODO bitdpでできる
    // station1->planet1.1->station1->planet1.2->station1->station2 のように移動
    const int PLANET = 1;
    const int STATION = 2;
    vector<pair<int, int>> ops;
    {
        int sid = pre_assign[0];
        int sid_init = sid;
        while (true) {
            for (int pid = 0; pid < N; pid++) {
                if (pre_assign[pid] == sid) {
                    ops.push_back({PLANET, pid});
                    ops.push_back({STATION, sid});
                }
            }
            sid = (sid + 1) % M;
            if (sid == sid_init) break;
            ops.push_back({STATION, sid});
        }
        ops.push_back({STATION, sid_init});
        ops.push_back({PLANET, 0});
    }
    // 出力
    for (int sid = 0; sid < M; sid++) {
        auto st = stations[sid];
        int i = st.i + 0.5;
        int j = st.j + 0.5;
        print(i, j);
    }
    print(ops.size());
    for (auto op : ops) {
        print(op.first, op.second + 1);
    }
}
int main() {
    ioinit();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        planets[i] = {i : double(a), j : double(b)};
    }
    solve();
    return 0;
}
0