結果

問題 No.96 圏外です。
ユーザー codershifthcodershifth
提出日時 2015-08-04 23:13:44
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 453 ms / 5,000 ms
コード長 8,078 bytes
コンパイル時間 1,776 ms
コンパイル使用メモリ 183,108 KB
実行使用メモリ 108,856 KB
最終ジャッジ日時 2024-06-06 16:03:31
合計ジャッジ時間 7,063 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
97,408 KB
testcase_01 AC 81 ms
97,280 KB
testcase_02 AC 80 ms
97,408 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 87 ms
97,920 KB
testcase_05 AC 82 ms
97,920 KB
testcase_06 AC 83 ms
98,304 KB
testcase_07 AC 87 ms
98,432 KB
testcase_08 AC 92 ms
98,836 KB
testcase_09 AC 97 ms
99,328 KB
testcase_10 AC 103 ms
99,712 KB
testcase_11 AC 110 ms
100,776 KB
testcase_12 AC 116 ms
101,772 KB
testcase_13 AC 142 ms
102,008 KB
testcase_14 AC 148 ms
103,628 KB
testcase_15 AC 183 ms
103,956 KB
testcase_16 AC 187 ms
106,424 KB
testcase_17 AC 185 ms
108,856 KB
testcase_18 AC 222 ms
108,148 KB
testcase_19 AC 212 ms
108,188 KB
testcase_20 AC 186 ms
105,660 KB
testcase_21 AC 227 ms
107,092 KB
testcase_22 AC 405 ms
105,276 KB
testcase_23 AC 453 ms
105,148 KB
testcase_24 AC 78 ms
97,280 KB
testcase_25 AC 146 ms
105,648 KB
testcase_26 AC 173 ms
107,884 KB
testcase_27 AC 159 ms
106,616 KB
権限があれば一括ダウンロードができます

ソースコード

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;

template<typename T>
struct Pt {
    T x, y;
    Pt(T x0, T y0) : x(x0), y(y0) {}
    Pt() :x(0),y(0) {}
    Pt(const Pt &other) :x(other.x),y(other.y) {}

    Pt &operator=(const Pt& other) { x = other.x; y = other.y; return *this; }
    const Pt operator+(const Pt &other) const { return Pt(other.x+x, other.y+y); }
    const Pt operator-(const Pt &other) const { return Pt(other.x-x, other.y-y); }
    Pt &operator+=(const Pt &other) { x += other.x; y += other.y; return *this; }
    Pt &operator-=(const Pt &other) { x -= other.x; y -= other.y; return *this; }
    Pt operator*(double r) const { return Pt(x*r, y*r); }
    bool operator==(const Pt &other) const { return (x==other.x && y==other.y); }
    bool operator!=(const Pt &other) const { return !(operator==(other)); }
    bool operator<(const Pt &other) const { return (x < other.x)? true : ((x==other.x)? (y < other.y) : false); }
    bool operator<=(const Pt &other) const { return (*this == other)? true : (*this < other); }
    bool operator>(const Pt &other) const { return (other < *this); }
    bool operator>=(const Pt &other) const { return (other <= *this); }
    double norm(void) const { return hypot(x, y); }

    // class method
    static double cross(const Pt &a, const Pt &b) { return ((double)a.y*b.x - (double)a.x*b.y); }
    static double dot(const Pt &a, const Pt &b)   { return (double)a.x*b.x+(double)a.y*b.y; }

    // O(n*log(n))
    static std::vector<Pt> convex_hull(std::vector<Pt> &ps) {
            std::sort(ps.begin(), ps.end());
            int k = 0;
            int n = ps.size();
            vector<Pt> qs(2*n);
            for (int i = 0; i < n; ++i)
            {
                while (k > 1 && cross(qs[k-1]-qs[k-2], ps[i]-qs[k-1]) <= 0)
                    --k;
                qs[k++] = ps[i];
            }
            for (int i = n-2, t = k; i >= 0; --i)
            {
                while (k > t && cross(qs[k-1]-qs[k-2], ps[i]-qs[k-1]) <= 0)
                    --k;
                qs[k++] = ps[i];
            }
            qs.resize(k-1);
            qs.shrink_to_fit();
            return std::move(qs);
    }
    // convex_diameter
    // O(n*log(n))
    static double convex_diameter(std::vector<Pt> &ps) {
            auto qs = convex_hull(ps);
            int  n = qs.size();
            auto dist = [](const Pt &a, const Pt &b) { return sqrt(dot(a-b, a-b)); };
            if (n == 2)
                return dist(qs[0], qs[1]);

            int i,j;
            i = j = 0;

            for (int k = 0; k < n; ++k)
            {
                if ( !(qs[i] < qs[k]) )
                    i = k;
                if (qs[j] < qs[k])
                    j = k;
            }

            double res = 0;
            int si = i, sj = j;
            while ( !(i == sj && j == si) )
            {
                res = max(res, dist(qs[i], qs[j]));
                int di = (i+1)%n;
                int dj = (j+1)%n;
                if (cross(qs[di]-qs[i], qs[dj]-qs[j]) < 0)
                    i = di;
                else
                    j = dj;
            }
            return res;
    }
    friend std::ostream &operator<<(std::ostream &os, const Pt &p) {
            os <<"("<<p.x<<","<<p.y<<")";
            return os;
    }
};
template<typename T>
Pt<T> operator*(double r, const Pt<T> &p) { return p*r; }



class UFTree {
    std::vector<int> par_;
    std::vector<int> rank_;
    int size_;
public:
    UFTree(int N) { init(N); }
    UFTree() {}
    ~UFTree() {}

    void init(int N) {
        par_.resize(N);
        rank_.resize(N, 0);
        for (int i = 0; i < N; ++i)
            par_[i] = i;
        size_ = N;
    }
    int find(int x) {
        assert(0 <= x && x < par_.size());
        if ( par_[x] == x )
            return x;
        else
            return ( par_[x] = find(par_[x]));
    }
    void unite(int x, int y) {
        assert(0 <= x && x < par_.size());
        assert(0 <= y && y < par_.size());
        x = find(x);
        y = find(y);
        if ( x == y )
            return;
        --size_;
        if ( rank_[x] < rank_[y] )
            par_[x] = y;
        else
        {
            par_[y] = x;
            if ( rank_[x] == rank_[y] )
                ++rank_[x];
        }
    }
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
    size_t size() { return size_; }
    // find 経由で par を更新してからでないと par へのアクセスは危険
    int operator[](size_t i) { return find(i); }
};

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;
    }
};

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