No.96 圏外です。

No.96 圏外です。 - yukicoder

• バケット法 + union find + convex hull + キャリパー法。
• バケット法以外は思いついた。無駄に kd 木とかないとダメなのかなぁと思っていたらバケット法でよかった。バケット法の実装は初めてなので勉強になった。
• x,y の制約を Easy のままにしていて RE してしまった。
• 下のコードにはないが自作の Pt class (点表現クラス) の operator < の実装をミスって、std::sort で segv してしまった。
  • std::sort に渡す less は a < b じゃないとダメってやつ。(a <= b じゃダメ) わりと有名なアレ。

class NoService {
public:
    void solve(void) {
            int N;
            cin>>N;

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

            //
            // Easy と違って N <= 120000 なので O(N^2) では間に合わない
            // 距離が 10 km 以内の中継局を同じグループとして、中継局をグループ化してやることが
            // できれば、凸包を作って(O(n*log(n)) からキャリパー法 (O(n)) が使える。
            //
            // union find 自体は高速なので、問題は (x,y) の周り 10km の (x',y') をどう求めるか
            // が問題となる。10km 以内の中継局を同じグループとみなすので、座標 x,y を
            // 10km x 10km のバケットで管理するバケット法を使う。
            //
            // 座標は整数なので 1 バケットに最大 100 個の点が入る。
            // (x,y) の周囲 10km 以内の点を見つけるのには (x,y) の所属するバケット周りの 9 バケット
            // (最大 900 点)をチェックすればよい。
            //
            // O(N*900) <= 108000000
            //
            // 制限時間 5 秒なのでなんとかまにあいそう？
            //

            // x,y の制限が小さいので配列でバケットが作れる (access O(1))

            UFTree uft(N);
            const int offset = 10000;
            const int B = 10;
            const int dx[] = {-1,0,1};
            const int dy[] = {-1,0,1};
            const int M = 2*offset/B; // 2000
            vector<vector<vector<int>>> bucket(M+1,vector<vector<int>>(M+1, vector<int>()));
            vector<Pt<int>> ps;
            REP(i,N)
            {
                int x,y;
                cin>>x>>y;
                ps.emplace_back(x,y);
                bucket[(x+offset)/B][(y+offset)/B].push_back(i);
            }
            // bucket を使って UFTree を更新
            REP(i,N)
            {
                int xi = (ps[i].x+offset)/B;
                int yi = (ps[i].y+offset)/B;

                // 隣接する 9 バケットを探索
                REP(ii,3)
                REP(jj,3)
                {
                    int xi2 = xi+dx[ii];
                    int yi2 = yi+dy[jj];
                    if (xi2 < 0 || xi2 > M || yi2 < 0 || yi2 > M)
                        continue;

                    for (auto k : bucket[xi2][yi2])
                    {
                        if (k == i)
                            continue;
                        if ( (ps[k]-ps[i]).norm() <= 10 )
                            uft.unite(k,i);
                    }
                }
            }

            vector<vector<Pt<int>>> group(N);
            REP(i,N)
                group[uft[i]].push_back(ps[i]);

            double ans = 0;
            REP(i,N)
            {
                if (uft[i]==i)
                    ans = max(ans, Pt<int>::convex_diameter(group[uft[i]]));
            }
            cout<<setprecision(20)<<ans+2<<endl;
    }
};