結果

問題 No.96 圏外です。
ユーザー atn112323
提出日時 2016-03-22 15:33:28
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,343 ms / 5,000 ms
コード長 17,430 bytes
コンパイル時間 4,810 ms
コンパイル使用メモリ 91,524 KB
実行使用メモリ 166,240 KB
最終ジャッジ日時 2024-12-24 08:36:25
合計ジャッジ時間 26,556 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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<Problem> {
        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<Integer> 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<Point> 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<Integer> ids = new ArrayList<>();
        }
        
        class Point implements Comparable<Point> {
            
            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<Integer> 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<parent.length; i++) {
                    parent[i] = i;
                    rank[i] = 0;
                }
            }
            public int find(int x) {
                if (parent[x] == x) {
                    return x;
                } else {
                    return parent[x] = find(parent[x]);
                }
            }
            public void unite(int x, int y) {
                x = find(x);
                y = find(y);
                if (x==y) {
                    return;
                }
                if (rank[x] < rank[y]) {
                    parent[x] = y;
                } else {
                    parent[y] = x;
                    if (rank[x] == rank[y]) {
                        rank[x]++;
                    }
                }
            }
            public boolean same(int x, int y) {
                return find(x) == find(y);
            }
        }
    }
    
    /**
     * This class is a solver to confirm the main solver.
     * This solver often works only for a problem with a small number setting.
     */
    class Solver2 implements IProblemSolver<Problem> {
        @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<parent.length; i++) {
                    parent[i] = i;
                    rank[i] = 0;
                }
            }
            int find(int x) {
                if (parent[x] == x) {
                    return x;
                } else {
                    return parent[x] = find(parent[x]);
                }
            }
            void unite(int x, int y) {
                x = find(x);
                y = find(y);
                if (x==y) {
                    return;
                }
                if (rank[x] < rank[y]) {
                    parent[x] = y;
                } else {
                    parent[y] = x;
                    if (rank[x] == rank[y]) {
                        rank[x]++;
                    }
                }
            }
            boolean same(int x, int y) {
                return find(x) == find(y);
            }
        }
    }
    
    class Factory implements IProblemFactory<Problem> {
        @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<Problem> processor;
    
    Main() {
        Init();
    }
    
    void Init() {
        ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();
        
        config.factory = new Factory();
        config.solver = new Solver();
        config.solver2 = new Solver2();
        config.comparator = new ResultComparator();
        
        processor = new ProblemProcessor<Problem>(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<P extends IProblem> {
        
        abstract P newProblem();
        abstract P newProblem(ProblemReader reader) throws IOException;
    }
    
    interface IProblemSolver<P extends IProblem> {
        
        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<P extends IProblem> {
        
        IProblemFactory<P> factory;
        
        ProblemCreator(IProblemFactory<P> factory) {
            this.factory = factory;
        }
        
        void create() throws FileNotFoundException {
            P problem = factory.newProblem();
            System.out.println(problem.toString());
        }
    }
    
    class ProblemSolverComparator<P extends IProblem> {
        
        IProblemFactory<P> factory;
        IProblemSolver<P> solver1, solver2;
        IResultComparator comparator;
        
        ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> 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<P extends IProblem> {
        
        IProblemFactory<P> factory;
        IProblemSolver<P> solver;
        
        ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> 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<P extends IProblem> {
        
        IProblemFactory<P> factory;
        
        IProblemSolver<P> solver, solver2;
        
        IResultComparator comparator;
    }
    
    class ProblemProcessor<P extends IProblem> {
        
        ProblemProcessorConfig<P> config;
        
        ProblemCreator<P> creator;
        ProblemSolverComparator<P> comparator;
        ProblemAnswerer<P> answerer;
        
        ProblemProcessor(ProblemProcessorConfig<P> config) {
            this.config = config;
            creator = new ProblemCreator<P>(config.factory);
            comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2, config.comparator);
            answerer = new ProblemAnswerer<P>(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(" ");
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0