結果

問題 No.96 圏外です。
ユーザー なおなお
提出日時 2014-12-07 19:35:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 250 ms / 5,000 ms
コード長 4,220 bytes
コンパイル時間 1,823 ms
コンパイル使用メモリ 180,980 KB
実行使用メモリ 114,432 KB
最終ジャッジ日時 2024-06-06 15:34:28
合計ジャッジ時間 6,839 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
97,404 KB
testcase_01 AC 73 ms
97,408 KB
testcase_02 AC 71 ms
97,408 KB
testcase_03 AC 72 ms
97,152 KB
testcase_04 AC 75 ms
97,744 KB
testcase_05 AC 78 ms
98,048 KB
testcase_06 AC 80 ms
98,432 KB
testcase_07 AC 84 ms
98,816 KB
testcase_08 AC 89 ms
99,584 KB
testcase_09 AC 96 ms
100,316 KB
testcase_10 AC 103 ms
100,552 KB
testcase_11 AC 115 ms
102,372 KB
testcase_12 AC 128 ms
104,028 KB
testcase_13 AC 141 ms
102,464 KB
testcase_14 AC 159 ms
106,004 KB
testcase_15 AC 186 ms
103,648 KB
testcase_16 AC 213 ms
109,152 KB
testcase_17 AC 235 ms
114,432 KB
testcase_18 AC 250 ms
111,104 KB
testcase_19 AC 244 ms
110,976 KB
testcase_20 AC 189 ms
102,184 KB
testcase_21 AC 194 ms
103,132 KB
testcase_22 AC 212 ms
100,872 KB
testcase_23 AC 214 ms
100,876 KB
testcase_24 AC 72 ms
97,408 KB
testcase_25 AC 186 ms
109,444 KB
testcase_26 AC 219 ms
112,896 KB
testcase_27 AC 195 ms
110,856 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