結果

問題 No.96 圏外です。
ユーザー parukiparuki
提出日時 2016-09-30 02:28:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,561 ms / 5,000 ms
コード長 4,431 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 194,492 KB
実行使用メモリ 349,276 KB
最終ジャッジ日時 2024-06-06 16:25:04
合計ジャッジ時間 12,588 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 50 ms
172,932 KB
testcase_05 AC 55 ms
173,212 KB
testcase_06 AC 62 ms
172,104 KB
testcase_07 AC 58 ms
150,404 KB
testcase_08 AC 89 ms
174,528 KB
testcase_09 AC 109 ms
177,688 KB
testcase_10 AC 102 ms
162,684 KB
testcase_11 AC 156 ms
181,632 KB
testcase_12 AC 283 ms
258,432 KB
testcase_13 AC 192 ms
172,636 KB
testcase_14 AC 281 ms
192,124 KB
testcase_15 AC 299 ms
173,804 KB
testcase_16 AC 402 ms
198,108 KB
testcase_17 AC 511 ms
343,920 KB
testcase_18 AC 494 ms
201,660 KB
testcase_19 AC 496 ms
202,552 KB
testcase_20 AC 463 ms
349,276 KB
testcase_21 AC 495 ms
211,896 KB
testcase_22 AC 1,561 ms
23,188 KB
testcase_23 AC 1,328 ms
233,516 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 384 ms
309,340 KB
testcase_26 AC 474 ms
335,192 KB
testcase_27 AC 427 ms
320,756 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define EPS 1e-10
struct V2{
    double x, y;
    V2(){}
    V2(double x_, double y_):x(x_),y(y_){}
    bool operator<(const V2 &p) const{
        return x!=p.x?x<p.x:y<p.y;
    }
    V2 operator+(V2 p)const{
        return V2(add(x,p.x), add(y,p.y));
    }
    V2 operator-(V2 p)const{
        return V2(add(x,-p.x), add(y,-p.y));
    }
    double dist()const{
        return sqrt(x*x+y*y);
    }
    static double add(double a, double b){
        return abs(a+b)<EPS*(abs(a)+abs(b))?0:a+b;
    }
};
V2 operator *(double k, V2 p){
    p.x *= k;
    p.y *= k;
    return p;
}
double dot(const V2 &a, const V2 &b){
    return V2::add(a.x*b.x, a.y*b.y);
}
double cross(const V2 &a, const V2 &b){
    return V2::add(a.x*b.y, -a.y*b.x);
}

int ccw(V2 a, V2 b, V2 c) {
    b = b-a; c = c-a;
    if(cross(b, c) > EPS) return +1;
    if(cross(b, c) < -EPS) return -1;
    if(dot(b, c) < -EPS) return +2;
    if (b.dist() < c.dist()) return -2;
    return 0;
}

vector<V2> convexHull(vector<V2> ps){
    int n = (int)ps.size();
    sort(begin(ps), end(ps));
    int k = 0;
    vector<V2> qs(n*2);
    for(int i=0; i<n; ++i){
        while(k > 1 && ccw(qs[k-2], qs[k-1], ps[i]) <= 0) k--;
        qs[k++] = ps[i];
    }
    for(int i=n-2, t=k; i>=0; --i){
        while(k>t && ccw(qs[k-2], qs[k-1], ps[i]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}

pair<V2,V2> mostDistantPair(const vector<V2> &ps){
    vector<V2> qs = convexHull(ps);
    int n = (int)qs.size();
    if(n==2)return make_pair(qs[0], qs[1]);

    int i=0, j=0;
    for(int k=0; k<n; ++k){
        if(!(qs[i]<qs[k])) i = k;
        if(qs[j]<qs[k]) j = k;
    }
    pair<V2, V2> res;
    double maxDis = 0, dis;
    int si = i, sj = j;
    while(i!=sj || j!=si){
        dis = (qs[i]-qs[j]).dist();
        if(dis>maxDis){
            maxDis = dis;
            res.first = qs[i];
            res.second = qs[j];
        }
        if(cross(qs[(i + 1) % n] - qs[i], qs[(j + 1) % n] - qs[j]) < 0)i = (i + 1) % n;
        else j = (j + 1) % n;
    }
    return res;
}

int sq(int x, int y){
    return x*x + y*y;
}

class UnionFind{
public:
    UnionFind(int _n):n(_n), cnt(_n), par(_n), rank(_n), size(_n, 1){
        for(int i=0;i<n;++i) par[i]=i;
    }
    int find(int k){
        return (k==par[k])?k:(par[k]=find(par[k]));
    }
    int operator[](int k){
        return find(k);
    }
    int getSize(int k){
        return size[find(k)];
    }
    void unite(int x, int y){
        x = find(x); y = find(y);
        if(x==y) return;
        --cnt;
        if(rank[x] < rank[y]){
            par[x] = y;
            size[y] += size[x];
        }else{
            par[y] = x;
            size[x] += size[y];
            if(rank[y] == rank[x]) ++rank[x];
        }
    }
    int count(){
        return cnt;
    }
private:
    int n, cnt;
    vector<int> par, rank, size;
};

bool A[20030][20030];

int main(){
    int N;
    map<pair<int, int>, int> M;
    cin >> N;
    vi X(N), Y(N);
    vector<pii> P(N);
    rep(i, N){
        scanf("%d%d", &X[i], &Y[i]);
        X[i] += 10010;
        Y[i] += 10010;
        P[i] = {X[i],Y[i]};
        M[P[i]] = i;
        A[X[i]][Y[i]] = 1;
    }

    UnionFind uf(N);
    rep(i, N){
        for(int x = X[i] - 10; x <= X[i] + 10; ++x)for(int y = Y[i] - 10; y <= Y[i] + 10; ++y){
            int d = sq(x - X[i], y - Y[i]);
            if(d&&d <= 100&&A[x][y]){
                uf.unite(i, M[mp(x, y)]);
            }
        }
    }

    double ans = 1;
    vector<vi> I(N);
    rep(i, N)I[uf[i]].push_back(i);
    vector<V2> V;
    rep(i, N){
        if(!sz(I[i]))continue;
        V.resize(sz(I[i]));
        rep(j, sz(I[i])){
            int k = I[i][j];
            V[j].x = X[k];
            V[j].y = Y[k];
        }
        auto p = mostDistantPair(V);
        double d = (p.first - p.second).dist();
        smax(ans, d + 2);
    }
    cout << setprecision(20) << ans << endl;
}
0