#include #include #include #include #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; using vvll=vector; using pll=pair; // using mint=modint; using BoostPoint=boost::polygon::point_data; using Voronoi=boost::polygon::voronoi_diagram; /** * 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 int sgn(T x) { return (x > 0) - (x < 0); } template 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 P; vector

convexHull(vector

pts) { if (sz(pts) <= 1) return pts; sort(all(pts)); vector

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 P; array hullDiameter(vector

S) { int n = sz(S), j = n < 2 ? 0 : 1; pair> 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 x(N),y(N); vectorboostpts; rep(i,0,N){ cin>>x[i]>>y[i]; boostpts.push_back({x[i],y[i]}); } if(N==0){ cout<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> groups=uf.groups(); ll best2=0; for(auto&ids:groups){ vector

pts; for(auto id:ids)pts.emplace_back(x[id],y[id]); vector

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<