結果

問題 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 #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0