結果
問題 | No.168 ものさし |
ユーザー |
![]() |
提出日時 | 2015-03-20 00:07:33 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 905 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 34,688 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 06:56:32 |
合計ジャッジ時間 | 1,064 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:29:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 29 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:32:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 32 | scanf("%lld %lld", X+i, Y+i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <cstring> #include <algorithm> int N; long long X[1001], Y[1001]; bool used[1001]; long long dist(int i, int j){ long long dx = std::abs(X[i] - X[j]), dy = std::abs(Y[i] - Y[j]); return dx * dx + dy * dy; } bool dfs(int u, long long limit){ used[u] = true; if(u == N){return true;} bool res = false; for(int i=1;i<=N;i++){ if(used[i]){continue;} if(dist(u, i) <= limit * limit){res |= dfs(i, limit);} } return res; } int main(){ scanf("%d", &N); for(int i=1;i<=N;i++){ scanf("%lld %lld", X+i, Y+i); } long long lb = 0ll, ub = 252521000ll; while(ub - lb > 1){ long long mid = (lb + ub) / 2 * 10; memset(used, 0, sizeof(used)); if(dfs(1, mid)){ ub = mid / 10; }else{ lb = mid / 10; } } printf("%lld\n", ub * 10); }