結果

問題 No.96 圏外です。
ユーザー なおなお
提出日時 2014-12-07 19:35:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 193 ms / 5,000 ms
コード長 4,220 bytes
コンパイル時間 1,612 ms
コンパイル使用メモリ 169,192 KB
実行使用メモリ 114,084 KB
最終ジャッジ日時 2023-08-25 21:21:12
合計ジャッジ時間 5,957 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
97,660 KB
testcase_01 AC 37 ms
97,820 KB
testcase_02 AC 37 ms
97,828 KB
testcase_03 AC 37 ms
97,560 KB
testcase_04 AC 39 ms
98,112 KB
testcase_05 AC 41 ms
98,364 KB
testcase_06 AC 43 ms
98,820 KB
testcase_07 AC 47 ms
99,112 KB
testcase_08 AC 52 ms
99,820 KB
testcase_09 AC 58 ms
100,560 KB
testcase_10 AC 68 ms
100,752 KB
testcase_11 AC 76 ms
102,464 KB
testcase_12 AC 91 ms
104,096 KB
testcase_13 AC 104 ms
102,500 KB
testcase_14 AC 116 ms
106,060 KB
testcase_15 AC 138 ms
103,576 KB
testcase_16 AC 156 ms
108,892 KB
testcase_17 AC 178 ms
114,084 KB
testcase_18 AC 190 ms
110,716 KB
testcase_19 AC 193 ms
110,760 KB
testcase_20 AC 156 ms
102,088 KB
testcase_21 AC 151 ms
103,176 KB
testcase_22 AC 184 ms
101,048 KB
testcase_23 AC 188 ms
100,940 KB
testcase_24 AC 36 ms
97,832 KB
testcase_25 AC 133 ms
109,384 KB
testcase_26 AC 165 ms
112,684 KB
testcase_27 AC 145 ms
110,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 想定解法: バケット + Union-Find + 凸包
// 計算量: O(NlogN)

// 参考
// http://www-ikn.ist.hokudai.ac.jp/~k-sekine/slides/convexhull.pdf
// http://www.prefield.com/algorithm/geometry/convex_hull.html
// http://www.prefield.com/algorithm/geometry/ccw.html
// http://www.prefield.com/algorithm/geometry/convex_diameter.html

#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 ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))

typedef complex<int> P;

const int MAXN = 120000, MINXY = -10000, MAXXY = +10000;
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 inprd(const P &a, const P &b){ return (conj(a) * b).real(); }
int outprd(const P &a, const P &b){ return (conj(a) * b).imag(); }

// http://www.prefield.com/algorithm/geometry/ccw.html
int ccw(int i, int j, int k) {
    P a(X[i],Y[i]),b(X[j],Y[j]),c(X[k],Y[k]);
    b -= a; c -= a;
    if(outprd(b, c) > 0)  return +1;    // counter clockwise
    if(outprd(b, c) < 0)  return -1;    // clockwise
    if(inprd(b, c) < 0)   return +2;    // c--a--b on line
    if(norm(b) < norm(c)) return -2;    // a--b--c on line
    return 0;
}

// http://www.prefield.com/algorithm/geometry/convex_hull.html
vector<int> convex_hull(vector<int> ps) {
    int n = ps.size(), k = 0;
    if(n < 3) return ps;
    sort(ps.begin(), ps.end(), [](int i, int j){
        return ((X[i]!=X[j])?(X[i]<X[j]):(Y[i]<Y[j]));
    });
    vector<int> ch(2*n);
    // lower-hull
    for(int i = 0; i < n; ch[k++] = ps[i++]){
        while(k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
    }
    // upper-hull
    for(int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]){
        while(k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
    }
    ch.resize(k-1);
    return ch;
}

vector<int> v[(MAXXY-MINXY)/10+1][(MAXXY-MINXY)/10+1];

int main(){
    //freopen("in/05.txt", "r", stdin);

    // 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);
        v[(Y[i]-MINXY)/10][(X[i]-MINXY)/10].push_back(i);
    }
    if(N == 0){
        cout << 1 << endl;
        return 0;
    }
    uf_ uf(N);

    // O(N*900)
    REP(i,N){
        int dx = (X[i]-MINXY)/10;
        int dy = (Y[i]-MINXY)/10;
        for(int y = -1; y <= 1; y++){
            if(dy+y < 0 || dy+y > (MAXXY-MINXY)/10) continue;
            for(int x = -1; x <= 1; x++){
                if(dx+x < 0 || dx+x > (MAXXY-MINXY)/10) continue;
                for(auto &j : v[dy+y][dx+x]){
                    if(i == j) continue;
                    if(norm(i,j) <= RANGE) uf.con(i,j);
                }
            }
        }
    }

    // 点集合を各クラスタに分割: O(NlogN)
    map<int, vector<int> > m;
    REP(i,N) m[uf.root(i)].push_back(i);

    // クラスタ毎に凸包を取って最遠点対を求める
    map<int,int> stat;
    int maxr = 0;
    for(auto &it : m){
        auto ch = convex_hull(it.second);
        int n = ch.size();
        stat[n]++;
        // このへんまでで最大でも N=1300 程度まで落ちるので O(N^2)
        REP(i,n) REP(j,n){
            if(i == j) continue;
            maxr = max(maxr, norm(ch[i],ch[j]));
        }
    }

    for(auto &v : stat) cerr << v.first << ":" << v.second << "/"; cerr<<endl;

    cout << fixed << setprecision(16) << sqrt((double)maxr)+2.0 << endl;
    return 0;
}
0