#1179361 (C++23) No.96 圏外です。

• 問題: No.96 圏外です。
• ユーザー: T1610
• 提出日時: 2026-08-26 16:55:14
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,926 bytes
• コンパイル時間: 4,702 ms
• コンパイル使用メモリ: 394,112 KB
• 実行使用メモリ: 31,284 KB
• 最終ジャッジ日時: 2026-08-26 16:56:04
• 合計ジャッジ時間: 28,466 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 20 TLE * 1 -- * 7

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (ll i = (s); i < (ll)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (ll i = (ll)(s - 1); i >= (ll)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T, typename U>
bool chmax(T& a, const U& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T, typename U>
bool chmin(T& a, const U& b) {
    if (a <= b) return false;
    a = b;
    return true;
}

void yes_no(bool f, string yes = "Yes", string no = "No") {
    cout << (f ? yes : no) << "\n";
}
//----------基本部分-----------------------------------------------------------------------
#define X real()
#define Y imag()
#define x(p) real(p)
#define y(p) imag(p)
#define curr(P, i) P[i]
#define next(P, i) P[(i + 1) % P.size()]
#define prev(P, i) P[(i + P.size() - 1) % P.size()]

using D = long double;

const D EPS = 1e-8;
const D INF = 1e12;
const D PI = acos(-1);
typedef complex<D> P;
typedef complex<D> point;
namespace std {
bool operator<(const P& a, const P& b) {
    return x(a) != x(b) ? x(a) < x(b) : y(a) < y(b);
}
} // namespace std
D cross(const P& a, const P& b) {
    return y(conj(a) * b);
}
D dot(const P& a, const P& b) {
    return x(conj(a) * b);
}

struct L : public vector<P> {
    L(const P& a, const P& b) {
        push_back(a);
        push_back(b);
    }
};
// 点の進行方向
int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    if (cross(b, c) > 0) return +1;   // counter clockwise
    if (cross(b, c) < 0) return -1;   // clockwise
    if (dot(b, c) < 0) return +2;     // c--a--b on line
    if (norm(b) < norm(c)) return -2; // a--b--c on line
    return 0;
}

// 凸包 - convex hull  同一直線上の点は除去（除去したくない場合は、ccw(...)<=0 ==> ccw(...)!=-1)             CGL_4_A
vector<point> convex_hull(vector<point> ps) {
    int n = ps.size(), k = 0;
    sort(ps.begin(), ps.end());
    vector<point> ch(2 * n);
    for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
        while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
    for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) // upper-hull
        while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
    ch.resize(k - 1);
    return ch;
}

void solve() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 1 << '\n';
        return;
    }
    dsu uf(n);
    using T = pair<int, int>;
    vector<T> ts(n);
    vector<P> pos(n);
    map<T, int> mp;
    rep(i, n) {
        int x, y;
        cin >> x >> y;
        pos[i] = {(D)x, (D)y};
        ts[i] = {x, y};
        mp[ts[i]] = i;
    }
    D ans = 1;
    const D eps = 1e-9;
    rep(i, n) {
        int x = ts[i].first, y = ts[i].second;
        for (int a = x - 10; a <= x + 10; ++a)
            for (int b = y - 10; b <= y + 10; ++b) {
                if (!mp.count({a, b})) continue;
                int j = mp[{a, b}];
                D x1 = pos[i].X, y1 = pos[i].Y;
                D x2 = pos[j].X, y2 = pos[j].Y;
                if (hypotl(x1 - x2, y1 - y2) < 10 + eps) {
                    uf.merge(i, j);
                }
            }
    }
    map<int, vector<P>> a;
    rep(i, n) a[uf.leader(i)].emplace_back(pos[i].X, pos[i].Y);
    for (auto&& [k, v] : a) {
        auto ch = convex_hull(v);
        int m = v.size();
        rep(i, m) rep(j, m) {
            D x1 = v[i].X, y1 = v[i].Y;
            D x2 = v[j].X, y2 = v[j].Y;
            D d = hypotl(x1 - x2, y1 - y2);
            chmax(ans, d + 2);
        }
    }
    cout << fixed << setprecision(15);
    cout << ans << "\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    rep(ti, t) solve();
    return 0;
}