結果

問題 No.96 圏外です。
コンテスト
ユーザー yantaro
提出日時 2026-11-16 16:46:37
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 5,184 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,043 ms
コンパイル使用メモリ 297,592 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-11-16 16:46:51
合計ジャッジ時間 14,005 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
//python3 expander.py main.cpp
//export CPLUS_INCLUDE_PATH="/home/yantaro/kyopro/ac-library-master"

//https://github.com/yantaro-yanchan/kyopro-library/tree/master/library

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lll = __int128_t;
using ulll = __uint128_t;

//using mint = modint; //mint::set_mod(M);
//using mint = modint998244353;
//using mint = modint1000000007;

template<class T> using pq = priority_queue<T>; //大きい順
template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; //小さい順

#define vec_unique(v) v.erase(unique(v.begin(), v.end()), v.end()) //重複削除
#define vec_iota(v) iota(v.begin(), v.end(), 0) //0, 1, 2, 3, ..., n - 1にセット
#define concat(a, b) a.insert(a.end(), b.begin(), b.end())
#define debug(x) cerr << #x << " = " << x << endl
#define maxvalue(array) *max_element(array.begin(), array.end())
#define minvalue(array) *min_element(array.begin(), array.end())
#define sumvalue(array) accumulate(array.begin(), array.end(), 0ll)
#define popcount(x) __builtin_popcountll(x)

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
//int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

#define INF 2e18
#define INF2 2e9

pair<int, int> operator- (const pair<int, int> &a, const pair<int, int> &b) {
    return {a.first - b.first, a.second - b.second};
}

ll cross(pair<int, int> l, pair<int, int> r) {
    return (ll)l.first * r.second - (ll)l.second * r.first;
}

vector<pair<int, int>> Convex_Hull(vector<pair<int, int>> p) {
    sort(p.begin(), p.end());
    int n = p.size();

    vector<pair<int, int>> ch;
    int k = 0;
    for(int i = 0; i < n; ch.push_back(p[i++]), k++) {
        while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) {
            ch.pop_back();
            k--;
        }
    }

    for(int i = n - 2, t = k + 1; i >= 0; ch.push_back(p[i--]), k++) {
        while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) {
            ch.pop_back();
            k--;
        }
    }

    ch.pop_back();
    k--;
    return ch;
}

ld Convex_Diameter(vector<pair<int, int>> p) {
    int n = p.size();
    int is = 0, js = 0;
    for(int i = 1; i < n; i++) {
        if(p[i].second > p[is].second) is = i;
        if(p[i].second < p[js].second) js = i;
    }

    auto dist = [&](pair<int, int> a, pair<int, int> b) -> ld {
        ld res = ((ll)a.first - b.first) * (a.first - b.first) + ((ll)a.second - b.second) * (a.second - b.second);
        res = sqrtl(res);
        return res;
    };

    ld maxdis = dist(p[is], p[js]);

    int maxi, maxj, i, j;
    i = maxi = is;
    j = maxj = js;
    do {
        if(cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0) {
            j = (j + 1) % n;
        } else {
            i = (i + 1) % n;
        }
        if(dist(p[i], p[j]) > maxdis) {
            maxdis = dist(p[i], p[j]);
            maxi = i, maxj = j;
        } 
    } while(i != is || j != js);
    return maxdis;
}

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    map<int, int> mp[20010];
    const int offset = 10000;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x += offset;
        y += offset;
        p[i] = {x, y};
        mp[x][y] = i;
    }

    if(n <= 2) {
        auto dist = [&](pair<int, int> a, pair<int, int> b) -> ll {
            return ((ll)a.first - b.first) * (a.first - b.first) + ((ll)a.second - b.second) * (a.second - b.second);
        };

        if(n == 0) cout << 1 << endl;
        else if(n == 1) cout << 2 << endl;
        else {
            if(dist(p[0], p[1]) <= 100) {
                ld ans = sqrtl(dist(p[0], p[1])) + 2;
                cout << fixed << setprecision(15) << ans << endl;
            } else {
                cout << 2 << endl;
            }
        }
        return;
    }

    dsu d(n);
    for(int i = 0; i < n; i++) {
        for(int j = -10; j <= 10; j++) {
            for(int k = 0; k <= 10; k++) {
                if(j * j + k * k > 100) break;
                
                auto[x, y] = p[i];
                if(i + j >= 0 && mp[x + j].count(y + k)) {
                    d.merge(i, mp[x + j][y + k]);
                }
                if(x + j >= 0 && mp[x + j].count(y - k)) {
                    d.merge(i, mp[x + j][y - k]);
                }
            }
        }
    }

    vector<vector<int>> vec(n);
    for(int i = 0; i < n; i++) {
        vec[d.leader(i)].push_back(i);
    }

    ld ans = 0.0;
    for(int i = 0; i < n; i++) {
        if(vec[i].size() == 0) continue;

        vector<pair<int, int>> p2;
        for(auto v : vec[i]) {
            p2.push_back(p[v]);
        }

        auto res = Convex_Hull(p2);
        ld d = Convex_Diameter(p2);
        ans = max(ans, d);
    }

    ans += 2;
    cout << fixed << setprecision(15) << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--) {
        solve();
    }
    //cout << fixed << setprecision(15) << << endl;
    return 0;
}
0