import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; public class Main { /** * This class represents a problem setting. */ class Problem implements IProblem { int N; int[][] XY; @Override public void set(ProblemReader reader) throws IOException { N = reader.nextInt(); XY = reader.nextIntArray2(N); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(StringUtils.toString(N) + "\n"); sb.append(StringUtils.toString(XY)); return sb.toString(); } } /** * Solver for the problem. * It's the most important part of codes in this file. */ class Solver implements IProblemSolver { int N; int[][] XY; @Override public String solve(Problem problem) { N = problem.N; XY = problem.XY; return StringUtils.toString(solve()); } private double solve() { if (N == 0) { return 1.0; } UnionFindTree uft = new UnionFindTree(N); Cell[][] cells = new Cell[4005][4005]; for (int i = 0; i < N; i++) { XY[i][0] += 10000; XY[i][1] += 10000; int cx = XY[i][0] / 5, cy = XY[i][1] / 5; for (int cxx = cx - 2; cxx <= cx + 2; cxx++) { for (int cyy = cy - 2; cyy <= cy + 2; cyy++) { if (0 <= cxx && 0 <= cyy && cells[cxx][cyy] != null) { for (int id : cells[cxx][cyy].ids) { if (dist2(i, id) <= 100) { uft.unite(i, id); } } } } } if (cells[cx][cy] == null) { cells[cx][cy] = new Cell(); } cells[cx][cy].ids.add(i); } Ids[] ids = new Ids[N]; for (int i = 0; i < N; i++) { int x = uft.find(i); if (ids[x] == null) { ids[x] = new Ids(); } ids[x].ids.add(i); } double max = 0.0; for (int i = 0; i < N; i++) { if (ids[i] != null) { max = Math.max(max, longest(ids[i].ids)); } } return max + 2.0; } private int dist2(int idx1, int idx2) { int dx = XY[idx1][0] - XY[idx2][0]; int dy = XY[idx1][1] - XY[idx2][1]; return dx * dx + dy * dy; } private int vc(Point p1, Point p2, Point p3) { int x1 = p3.x - p1.x, y1 = p3.y - p1.y; int x2 = p2.x - p1.x, y2 = p2.y - p1.y; return y2 * x1 - x2 * y1; } private int dist2(Point p1, Point p2) { int dx = p1.x - p2.x, dy = p1.y - p2.y; return dx * dx + dy * dy; } private double longest(List ids) { Point[] points = new Point[ids.size()]; for (int i = 0; i < ids.size(); i++) { points[i] = new Point(XY[ids.get(i)][0], XY[ids.get(i)][1]); } Arrays.sort(points); List ps = new ArrayList<>(); for (Point p : points) { while (ps.size() >= 2 && vc(ps.get(ps.size() - 2), ps.get(ps.size() - 1), p) <= 0) { ps.remove(ps.size() - 1); } ps.add(p); } int n = ps.size(); for (int i = points.length - 2; i >= 0; i--) { Point p = points[i]; while (ps.size() > n && vc(ps.get(ps.size() - 2), ps.get(ps.size() - 1), p) <= 0) { ps.remove(ps.size() - 1); } ps.add(p); } ps.remove(ps.size() - 1); double max = 0.0; int idx = 0; for (int i = 0; i < ps.size() && idx < ps.size(); i++) { Point p1 = ps.get(i); int dist2 = dist2(p1, ps.get(idx)); for (;;) { int d2 = dist2(p1, ps.get((idx + 1) % ps.size())); if (d2 > dist2) { dist2 = d2; idx++; } else { break; } } max = Math.max(max, Math.sqrt(dist2)); } return max; } class Cell { List ids = new ArrayList<>(); } class Point implements Comparable { int x, y; Point(int x, int y) { this.x = x; this.y = y; } @Override public int compareTo(Point point) { if (x != point.x) { return x - point.x; } else { return y - point.y; } } } class Ids { List ids = new ArrayList<>(); } class UnionFindTree { private int[] parent; private int[] rank; public UnionFindTree(int size) { parent = new int[size]; rank = new int[size]; init(); } public void init() { for (int i=0; i { @Override public String solve(Problem problem) { int N = problem.N; int[][] XY = problem.XY; return StringUtils.toString(solve(N, XY)); } private double solve(int N, int[][] XY) { if (N == 0) { return 1.0; } UnionFindTree uft = new UnionFindTree(N); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { int d2 = (XY[i][0] - XY[j][0]) * (XY[i][0] - XY[j][0]) + (XY[i][1] - XY[j][1]) * (XY[i][1] - XY[j][1]); if (d2 <= 10 * 10) { uft.unite(i, j); } } } int max = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (uft.same(i, j)) { int d2 = (XY[i][0] - XY[j][0]) * (XY[i][0] - XY[j][0]) + (XY[i][1] - XY[j][1]) * (XY[i][1] - XY[j][1]); max = Math.max(max, d2); } } } return Math.sqrt(max) + 2; } class UnionFindTree { private int[] parent; private int[] rank; UnionFindTree(int size) { parent = new int[size]; rank = new int[size]; init(); } void init() { for (int i=0; i { @Override public Problem newProblem() { int N = 10000; int[][] xys = new int[N][2]; int idx = 0; for (int x = 0; x < 100; x++) { for (int y = 0; y < 100; y++) { xys[idx++] = new int[]{x, y}; } } Random rng = new Random(); for (int i = 0; i < N; i++) { int rnd = rng.nextInt(N - i) + i; int[] tmp = xys[i]; xys[i] = xys[rnd]; xys[rnd] = tmp; } Problem problem = new Problem(); problem.N = N; problem.XY = xys; return problem; } @Override public Problem newProblem(ProblemReader reader) throws IOException { Problem problem = new Problem(); problem.set(reader); return problem; } } class ResultComparator implements IResultComparator { @Override public boolean same(String res1, String res2) { return res1.equals(res2); } } ProblemProcessor processor; Main() { Init(); } void Init() { ProblemProcessorConfig config = new ProblemProcessorConfig<>(); config.factory = new Factory(); config.solver = new Solver(); config.solver2 = new Solver2(); config.comparator = new ResultComparator(); processor = new ProblemProcessor(config); } void process(String mode) throws IOException { processor.process(mode); } public static void main(String args[]) throws IOException { // "create", "debug", and "solve" String mode = "solve"; new Main().process(mode); } /* Common library */ interface IProblem { abstract void set(ProblemReader reader) throws IOException; } interface IProblemFactory

{ abstract P newProblem(); abstract P newProblem(ProblemReader reader) throws IOException; } interface IProblemSolver

{ abstract String solve(P problem); } interface IResultComparator { abstract boolean same(String res1, String res2); } class ProblemReader { BufferedReader br = null; ProblemReader() { br = new BufferedReader(new InputStreamReader(System.in)); } int nextInt() throws IOException { return StringUtils.toInt(br.readLine()); } long nextLong() throws IOException { return StringUtils.toLong(br.readLine()); } double nextDouble() throws IOException { return StringUtils.toDouble(br.readLine()); } String nextString() throws IOException { return br.readLine(); } int[] nextIntArray() throws IOException { return StringUtils.toIntArray(br.readLine()); } long[] nextLongArray() throws IOException { return StringUtils.toLongArray(br.readLine()); } double[] nextDoubleArray() throws IOException { return StringUtils.toDoubleArray(br.readLine()); } String[] nextStringArray() throws IOException { return StringUtils.toStringArray(br.readLine()); } int[] nextIntArray(int n) throws IOException { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } long[] nextLongArray(int n) throws IOException { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } double[] nextDoubleArray(int n) throws IOException { double[] a = new double[n]; for (int i = 0; i < n; i++) { a[i] = nextDouble(); } return a; } String[] nextStringArray(int n) throws IOException { String[] strs = new String[n]; for (int i = 0; i < n; i++) { strs[i] = nextString(); } return strs; } int[][] nextIntArray2(int n) throws IOException { int[][] a = new int[n][]; for (int i = 0; i < n; i++) { a[i] = nextIntArray(); } return a; } long[][] nextLongArray2(int n) throws IOException { long[][] a = new long[n][]; for (int i = 0; i < n; i++) { a[i] = nextLongArray(); } return a; } double[][] nextDoubleArray2(int n) throws IOException { double[][] a = new double[n][]; for (int i = 0; i < n; i++) { a[i] = nextDoubleArray(); } return a; } String[][] nextStringArray2(int n) throws IOException { String[][] strs = new String[n][]; for (int i = 0; i < n; i++) { strs[i] = nextStringArray(); } return strs; } void close() throws IOException { if (br != null) { br.close(); } } } class ProblemCreator

{ IProblemFactory

factory; ProblemCreator(IProblemFactory

factory) { this.factory = factory; } void create() throws FileNotFoundException { P problem = factory.newProblem(); System.out.println(problem.toString()); } } class ProblemSolverComparator

{ IProblemFactory

factory; IProblemSolver

solver1, solver2; IResultComparator comparator; ProblemSolverComparator(IProblemFactory

factory, IProblemSolver

solver1, IProblemSolver

solver2, IResultComparator comparator) { this.factory = factory; this.solver1 = solver1; this.solver2 = solver2; this.comparator = comparator; } void compare() throws IOException { ProblemReader reader = null; try { reader = new ProblemReader(); P problem = factory.newProblem(reader); String res1 = solver1.solve(problem); String res2 = solver2.solve(problem); if (comparator.same(res1, res2)) { System.out.println(res1); } else { System.err.println(res1 + " " + res2); } } finally { if (reader != null) { reader.close(); } } } } class ProblemAnswerer

{ IProblemFactory

factory; IProblemSolver

solver; ProblemAnswerer(IProblemFactory

factory, IProblemSolver

solver) { this.factory = factory; this.solver = solver; } void answer() throws IOException { ProblemReader reader = null; try { reader = new ProblemReader(); P problem = factory.newProblem(reader); String res = solver.solve(problem); System.out.println(res); } finally { if (reader != null) { reader.close(); } } } } class ProblemProcessorConfig

{ IProblemFactory

factory; IProblemSolver

solver, solver2; IResultComparator comparator; } class ProblemProcessor

{ ProblemProcessorConfig

config; ProblemCreator

creator; ProblemSolverComparator

comparator; ProblemAnswerer

answerer; ProblemProcessor(ProblemProcessorConfig

config) { this.config = config; creator = new ProblemCreator

(config.factory); comparator = new ProblemSolverComparator

(config.factory, config.solver, config.solver2, config.comparator); answerer = new ProblemAnswerer

(config.factory, config.solver); } void process(String mode) throws IOException { switch (mode) { case "create": creator.create(); break; case "debug": comparator.compare(); break; case "solve": answerer.answer(); break; } } } static class StringUtils { static String toString(int a) { return String.valueOf(a); } static String toString(long a) { return String.valueOf(a); } static String toString(double a) { return String.valueOf(a); } static String toString(String str) { return str; } static String toString(int[] a, String delimiter) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + delimiter); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(long[] a, String delimiter) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + delimiter); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(double[] a, String delimiter) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + delimiter); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(String[] strs, String delimiter) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < strs.length; i++) { if (i < strs.length - 1) { sb.append(strs[i] + delimiter); } else { sb.append(strs[i]); } } return sb.toString(); } static String toString(int[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(long[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(double[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(String[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static int toInt(String s) { return Integer.parseInt(s); } static long toLong(String s) { return Long.parseLong(s); } static double toDouble(String s) { return Double.parseDouble(s); } static int[] toIntArray(String s) { String[] tokens = s.split(" "); int[] a = new int[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Integer.parseInt(tokens[i]); } return a; } static long[] toLongArray(String s) { String[] tokens = s.split(" "); long[] a = new long[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Long.parseLong(tokens[i]); } return a; } static double[] toDoubleArray(String s) { String[] tokens = s.split(" "); double[] a = new double[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Double.parseDouble(tokens[i]); } return a; } static String[] toStringArray(String s) { return s.split(" "); } } }