#1191647 (C++23(gcc16)) No.94 圏外です。(EASY)

• 問題: No.94 圏外です。(EASY)
• ユーザー: C
• 提出日時: 2026-10-06 01:18:41
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3 ms / 5,000 ms
• コード長: 5,270 bytes
• コンパイル時間: 9,689 ms
• コンパイル使用メモリ: 478,160 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-10-06 01:18:57
• 合計ジャッジ時間: 9,152 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
other	AC * 22

コンパイルメッセージ

main.cpp:31:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
   31 | #pragma once
      |         ^~~~
main.cpp:80:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
   80 | #pragma once
      |         ^~~~
main.cpp:107:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
  107 | #pragma once
      |         ^~~~

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using pll=pair<ll,ll>;

// using mint=modint;

using BoostPoint=boost::polygon::point_data<int>;
using Voronoi=boost::polygon::voronoi_diagram<double>;

/**
 * Author: Ulf Lundstrom
 * Date: 2009-02-26
 * License: CC0
 * Source: My head with inspiration from tinyKACTL
 * Description: Class to handle points in the plane.
 * 	T can be e.g. double or long long. (Avoid int.)
 * Status: Works fine, used a lot
 */
#pragma once

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

/**
 * Author: Stjepan Glavina, chilli
 * Date: 2019-05-05
 * License: Unlicense
 * Source: https://github.com/stjepang/snippets/blob/master/convex_hull.cpp
 * Description:
\\\begin{minipage}{75mm}
Returns a vector of the points of the convex hull in counter-clockwise order.
Points on the edge of the hull between two other points are not considered part of the hull.
\end{minipage}
\begin{minipage}{15mm}
\vspace{-6mm}
\includegraphics[width=\textwidth]{content/geometry/ConvexHull}
\vspace{-6mm}
\end{minipage}
 * Time: O(n \log n)
 * Status: stress-tested, tested with kattis:convexhull
*/
#pragma once


typedef Point<ll> P;
vector<P> convexHull(vector<P> pts) {
	if (sz(pts) <= 1) return pts;
	sort(all(pts));
	vector<P> h(sz(pts)+1);
	int s = 0, t = 0;
	for (int it = 2; it--; s = --t, reverse(all(pts)))
		for (P p : pts) {
			while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
			h[t++] = p;
		}
	return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

/**
 * Author: Oleksandr Bacherikov, chilli
 * Date: 2019-05-05
 * License: Boost Software License
 * Source: https://codeforces.com/blog/entry/48868
 * Description: Returns the two points with max distance on a convex hull (ccw,
 * no duplicate/collinear points).
 * Status: stress-tested, tested on kattis:roberthood
 * Time: O(n)
 */
#pragma once

typedef Point<ll> P;
array<P, 2> hullDiameter(vector<P> S) {
	int n = sz(S), j = n < 2 ? 0 : 1;
	pair<ll, array<P, 2>> res({0, {S[0], S[0]}});
	rep(i,0,j)
		for (;; j = (j + 1) % n) {
			res = max(res, {(S[i] - S[j]).dist2(), {S[i], S[j]}});
			if ((S[(j + 1) % n] - S[j]).cross(S[i + 1] - S[i]) >= 0)
				break;
		}
	return res.second;
}

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

    /**
     * Voronoi図の隣接関係（Delaunay辺）を使って連結成分をO(NlogN)で構築する。
     * EMSTはDelaunayグラフに含まれ、距離10より大きいEMST辺を削除した後の連結成分は
     *「距離10以下の中継局同士を結んだグラフ」の連結成分と一致する。
     * 
     * 各連結成分では最遠点対は凸包上にあるので
     * 凸包+rotating calipersで直径をO(KlogK)で求める。
     */

    int N;
    cin>>N;
    vector<int> x(N),y(N);
    vector<BoostPoint>boostpts;
    rep(i,0,N){
        cin>>x[i]>>y[i];
        boostpts.push_back({x[i],y[i]});
    }

    if(N==0){
        cout<<fixed<<setprecision(12)<<1.0L<<'\n';
        return 0;
    }

    Voronoi vd;
    boost::polygon::construct_voronoi(boostpts.begin(),boostpts.end(),&vd);

    dsu uf(N);

    for(auto&e:vd.edges()){
        int u=e.cell()->source_index();
        int v=e.twin()->cell()->source_index();
        if(u>v)continue;
        int dx=x[u]-x[v],dy=y[u]-y[v];
        if(dx*dx+dy*dy<=100)uf.merge(u,v);
    }

    vector<vector<int>> groups=uf.groups();
    ll best2=0;

    for(auto&ids:groups){
        vector<P>pts;
        for(auto id:ids)pts.emplace_back(x[id],y[id]);
        vector<P>hull=convexHull(pts);
        auto [a,b]=hullDiameter(hull);
        ll dist2=(a-b).dist2();
        best2=max(best2,dist2);
    }

    ld ans=sqrtl((ld)best2)+2.0L;
    cout<<fixed<<setprecision(12)<<ans<<'\n';

}