結果
問題 |
No.2612 Close the Distance
|
ユーザー |
![]() |
提出日時 | 2024-06-17 19:34:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,312 bytes |
コンパイル時間 | 630 ms |
コンパイル使用メモリ | 57,760 KB |
最終ジャッジ日時 | 2025-02-21 23:07:32 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 23 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:57:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 57 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:58:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2612.cc: No.2612 Close the Distance - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 200000; const int MAX_D = 2000000000; /* typedef */ using ll = long long; using vi = vector<int>; /* global variables */ int xs[MAX_N], ys[MAX_N]; /* subroutines */ inline int md(int i, int j) { return abs(xs[j] - xs[i]) + abs(ys[j] - ys[i]); } int mostdist(vi &v, int st) { int maxd = -1, maxu = -1; for (auto u: v) { int d = md(st, u); if (maxd < d) maxd = d, maxu = u; } return maxu; } bool check(int n, int u0, int u1, int d) { vi v; for (int u = 0; u < n; u++) if (md(u0, u) > d && md(u1, u) > d) v.push_back(u); if (v.empty()) return true; int u2 = mostdist(v, v[0]); int u3 = mostdist(v, u2); return md(u2, u3) <= d; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); vi v0(n); for (int i = 0; i < n; i++) v0[i] = i; int u0 = mostdist(v0, 0); int u1 = mostdist(v0, u0); //printf(" u0=%d, u1=%d\n", u0, u1); int d0 = -1, d1 = MAX_D; while (d0 + 1 < d1) { int d = ((ll)d0 + d1) / 2; if (check(n, u0, u1, d)) d1 = d; else d0 = d; } printf("%d\n", d1); return 0; }