結果

問題 No.96 圏外です。
ユーザー なお
提出日時 2014-12-07 19:35:04
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 233 ms / 5,000 ms
コード長 4,220 bytes
コンパイル時間 2,054 ms
コンパイル使用メモリ 180,716 KB
実行使用メモリ 114,432 KB
最終ジャッジ日時 2024-12-24 07:39:25
合計ジャッジ時間 6,827 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0