結果
問題 | No.94 圏外です。(EASY) |
ユーザー |
|
提出日時 | 2014-11-09 19:04:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,964 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 162,204 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 07:11:44 |
合計ジャッジ時間 | 2,874 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
// 想定解法: Union-Find + 同一ノード内全探索 #include <bits/stdc++.h> using namespace std; void rc(int v,int mn,int mx){if(v<mn||mx<v){cerr<<"error"<<endl;exit(1);}} #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) #define FOR(i, f, t) for(int(i)=(f);(i)<(t);(++i)) const int MAXN = 1000, MINXY = -1000, MAXXY = +1000; const int RANGE = 10*10; int N, X[MAXN+1], Y[MAXN+1]; int norm(int i,int j){int x=X[i]-X[j],y=Y[i]-Y[j];return x*x+y*y;} class uf_ { public: vector<int> node; uf_(int n) : node(n, -1){;} void con(int n, int m){ n = root(n); m = root(m); if(n == m) return; node[n] += node[m]; node[m] = n; } bool is_con(int n, int m){ return root(n) == root(m); } int root(int n){ return (node[n] < 0) ? n : node[n] = root(node[n]); } int size(int n){ return -node[root(n)]; } }; int main(){ // input : O(N) cin >> N; rc(N, 0, MAXN); REP(i, N){ cin >> X[i] >> Y[i]; rc(X[i], MINXY, MAXXY); rc(Y[i], MINXY, MAXXY); } if(N == 0){ cout << 1 << endl; return 0; } uf_ uf(N); // O(N^2) REP(i,N) REP(j,N){ if(i == j) continue; int r = norm(i,j); if(r <= RANGE){ uf.con(i,j); } } // O(N^2) int maxr = 0; REP(i,N) REP(j,N){ if(i == j) continue; if(uf.is_con(i,j)){ maxr = max(maxr, norm(i,j)); } } //fprintf(stderr, "(%d,%d)-(%d,%d)\n",X[a],Y[a],X[b],Y[b]); cout << fixed << setprecision(9) << sqrt((double)maxr)+2.0 << endl; return 0; } /* 解説 各点と周囲の点が10km以内にいるか判定して、10km以内の点を次々と連結していく。 つながった点に対して、全点同士で距離判定して最大を取る。 最大でも 2,000,000ループくらい Union-FindじゃなくてBFSでもOK */