結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー codershifth
提出日時 2015-08-04 08:40:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 2,331 bytes
コンパイル時間 1,471 ms
コンパイル使用メモリ 172,420 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 07:38:06
合計ジャッジ時間 2,324 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class NoServiceEasy {
public:
    ll   square(int x) { return x*x; }
    ll   dist2(const pair<int,int> &a, const pair<int,int> &b) {
            return square(a.first-b.first)+square(a.second-b.second);
    }
    void solve(void) {
            int N;
            cin>>N;

            // 中継局がないときは 1km が最大
            if (N==0)
            {
                cout<<1<<endl;
                return;
            }

            vector<pair<int,int>> xy;
            REP(i,N)
            {
                int x,y;
                cin>>x>>y;
                xy.emplace_back(x,y);
            }

            // 10km 以内にある中継局をつなぐことで作ったグループにたいして
            // そのグループ内での最長距離をもとめればよい
            vector<vector<int>> tree(N);
            REP(i,N)
            FOR(j,i+1,N)
            {
                if (dist2(xy[i],xy[j]) <= 10*10)
                {
                    tree[i].push_back(j);
                    tree[j].push_back(i);
                }
            }

            vector<bool> vis(N,false);
            vector<ll>   d2(N,0);
            function<void(int,int)> dfs = [&](int x, int root) {
                if (vis[x])
                    return;
                vis[x] = true;
                d2[root] = max(d2[root], dist2(xy[x], xy[root]));
                for (auto y : tree[x])
                {
                    if (vis[y])
                        continue;
                    dfs(y, root);
                }
            };

            // 木ではなく森になっているかもしれないので根を変えて試す
            // O(N^2)
            REP(root,N)
            {
                fill(RANGE(vis),false);
                dfs(root,root);
            }
            ll maxD2 = *max_element(RANGE(d2));
            cout<<setprecision(20)<<sqrt(maxD2)+2<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new NoServiceEasy();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0