結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 17:38:28 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 1,000 ms |
コード長 | 2,180 bytes |
コンパイル時間 | 752 ms |
実行使用メモリ | 6,952 KB |
スコア | 22,514 |
最終ジャッジ日時 | 2022-07-30 17:38:53 |
合計ジャッジ時間 | 4,093 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#define rep(i, n) for (int i = 0; i < (int)(n); i++)using namespace std;int N, M;int ALPHA = 5;vector<pair<int, int>> position_list; // [0 : N) ... planet, [N : N + M) ... stationint get_distance(int a, int b) {int alpha = 1;if (a < N) {alpha *= ALPHA;}if (b < N) {alpha *= ALPHA;}auto& p = position_list[a];auto& q = position_list[b];return alpha * (p.first - q.first) * (p.first - q.first) + (p.second - q.second) * (p.second - q.second);}int main() {cin >> N >> M;position_list.assign(N + M, make_pair(0, 0));rep (i, N) {cin >> position_list[i].first >> position_list[i].second;}position_list[N + 0] = make_pair(0, 0);position_list[N + 1] = make_pair(0, 500);position_list[N + 2] = make_pair(0, 1000);position_list[N + 3] = make_pair(500, 0);position_list[N + 4] = make_pair(500, 1000);position_list[N + 5] = make_pair(1000, 0);position_list[N + 6] = make_pair(1000, 500);position_list[N + 7] = make_pair(1000, 1000);size_t max_ans_size = 100'000;vector<int> ans;rep (i, N + M) {rep (j, N + M) {if (i != j) {ans.push_back(i);ans.push_back(j);}}}int v, w;int max_dist = -1;rep (i, N + M) {rep (j, N + M) {if (int d = get_distance(i, j); d > max_dist) {max_dist = d;v = i;w = j;}}}while (ans.size() < max_ans_size - 1) {if ((int)ans.size() % 2) {ans.push_back(v);} else {ans.push_back(w);}}ans.push_back(0);rep (i, M) {auto& [x, y] = position_list[N + i];cout << x << " " << y << "\n";}cout << (int)ans.size() << "\n";rep (i, (int)ans.size()) {int x = ans[i];if (x >= N) {cout << 2 << " " << x - N + 1 << "\n";} else {cout << 1 << " " << x + 1 << "\n";}}return 0;}