結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>// clang-format offusing 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;}