結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー GOTKAKO
提出日時 2025-07-01 04:51:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 5,149 bytes
コンパイル時間 2,815 ms
コンパイル使用メモリ 225,348 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-07-01 04:51:28
合計ジャッジ時間 3,821 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Point{
    public:
    T x,y;
    Point() : x(0),y(0) {}
    Point(T a,T b) : x(a),y(b) {}
    Point &operator=(const Point &b) = default;
    Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
    Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
    Point operator+=(const Point &b){return *this=*this+b;}
    Point operator-=(const Point &b){return *this=*this-b;}
    bool operator==(const Point &b){return x==b.x && y==b.y;}
    bool operator!=(const Point &b){return x!=b.x || y!=b.y;}
    bool operator<(const Point &b){
        if(x == b.x) return y < b.y;
        else return x < b.x; 
    }
    bool operator<=(const Point &b){return (*this) < b || (*this) == b;}
    bool operator>(const Point &b){return !((*this) <= b);}
    bool operator>=(const Point &b){return !((*this) < b);}

    friend T inner(const Point a,const Point b){return a.x*b.x+a.y*b.y;}
    friend T cross(const Point a,const Point b){return a.x*b.y-a.y*b.x;}
    friend T twodist(const Point a,const Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//2乗で返す.
};
template<typename T>
istream &operator>>(istream &is,Point<T> &a){
    is >> a.x >> a.y;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,Point<T> &a){
    os << a.x << " " << a.y;
    return os;
}
template<typename T>
vector<Point<T>> Convexhull(vector<Point<T>> &P){
    //(x,y)が最小の点から時計回りに頂点を返す.
    //(xi,yi)と(xi+1,yi+1)は辺になる |P|=1の時注意.
    sort(P.begin(),P.end());
    P.erase(unique(P.begin(),P.end()),P.end());
    if(P.size() == 0) return {};
    if(P.size() == 1) return {P.at(0),P.at(0)};
    vector<Point<T>> A,B;
    for(auto &p1 : P){
        while(A.size() >= 2){
            auto &p2 = A.at(A.size()-1);
            auto &p3 = A.at(A.size()-2);
            T check = cross(p2-p1,p3-p2);
            if(check <= 0) A.pop_back();
            else break;
        }
        A.push_back(p1);
    }
    for(auto &p1 : P){
        while(B.size() >= 2){
            auto &p2 = B.at(B.size()-1);
            auto &p3 = B.at(B.size()-2);
            T check = cross(p2-p1,p3-p2);
            if(check >= 0) B.pop_back();
            else break;
        }
        B.push_back(p1);
    }
    for(int i=B.size()-2; i>=0; i--) A.push_back(B.at(i));
    return A;
}

class UnionFind{
    private:
    vector<int> par,siz;
    public:
    UnionFind(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){ //連結成分の代表頂点を返す.
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
    bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す.
        u = root(u),v = root(v);
        if(u == v) return false;
 
        if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size.
        par.at(v) = u;
        siz.at(u) += siz.at(v);
        return true;
    }
    bool issame(int u, int v){ //同じ連結成分ならtrue.
        if(root(u) == root(v)) return true;
        else return false;
    }
    int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す.
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    if(N == 0){cout << 1 << endl; return 0;}
    vector<Point<int>> P(N);
    for(auto &p : P) cin >> p,p.x += 10000,p.y += 10000;
    
    map<pair<int,int>,int> M;
    const int n = 20000;
    vector<vector<pair<int,int>>> Xs(n+1);
    for(int i=0; i<N; i++) Xs.at(P.at(i).x).push_back({P.at(i).y,i});
    for(auto &x : Xs) sort(x.begin(),x.end());

    vector<int> OK(11);
    for(int i=0; i<=10; i++){
        for(int k=0; ; k++){
            int diff = i*i+k*k;
            if(diff <= 100) OK.at(i) = k;
            else break;
        }
    }

    UnionFind Z(N);
    for(int i=0; i<N; i++){
        auto [x,y] = P.at(i);
        for(int dx=0; dx<=10; dx++,x++){
            if(x > 20000) break;
            int ly = y-OK.at(dx),ry = y+OK.at(dx);
            auto &X = Xs.at(x);
            int pos = lower_bound(X.begin(),X.end(),pair{ly,-1})-X.begin();
            while(pos < X.size() && X.at(pos).first <= ry) Z.unite(i,X.at(pos).second),pos++;
        }
    }

    vector<vector<int>> G(N);
    for(int i=0; i<N; i++) G.at(Z.root(i)).push_back(i);
    
    double answer = 2;
    for(auto &g : G){
        if(g.size() <= 1) continue;
        
        vector<Point<int>> now;
        for(auto &p : g) now.push_back(P.at(p));

        auto con = Convexhull(now);
        con.pop_back();
        int pos = 0,n = con.size();
        for(int i=0; i<n; i++){
            while(true){
                int one = twodist(con.at(i),con.at(pos)),two = twodist(con.at(i),con.at((pos+1)%n));
                if(one < two){
                    answer = max(answer,sqrt(two)+2);
                    pos++;
                    if(pos == n) pos = 0;
                }
                else{answer = max(answer,sqrt(one)+2); break;}
            }
        }
    }
    cout << fixed << setprecision(20) << answer << endl;
}
0