結果

問題 No.168 ものさし
ユーザー kenkoooo
提出日時 2015-03-20 00:43:10
言語 Java
(openjdk 23)
結果
AC  
実行時間 678 ms / 2,000 ms
コード長 3,135 bytes
コンパイル時間 2,973 ms
コンパイル使用メモリ 87,532 KB
実行使用メモリ 62,640 KB
最終ジャッジ日時 2024-12-24 06:59:42
合計ジャッジ時間 9,938 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Main {
    public static void main(String[] args) {
        int N = nextInt();
        int[] x = new int[N];
        int[] y = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = nextInt();
            y[i] = nextInt();
        }
        Kruscal g = new Kruscal(N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                long dx = x[i] - x[j];
                long dy = y[i] - y[j];
                long distSq = dx * dx + dy * dy;
                long d = (sqrtCeil(distSq) + 9) / 10 * 10;
                g.addBidirectionalEdge(i, j, (int) d);
            }
        }
        System.out.println(g.minCost());
    }
    static long sqrtCeil(long n) {
        long l = 0;
        long r = 2000000000;
        while (l + 1 < r) {
            // (l+r)/2を超えない整数
            long c = (l + r) >>> 1;
            if (c * c >= n) {
                r = c;
            } else {
                l = c;
            }
        }
        return r;
    }
    static int nextInt() {
        int c;
        try {
            c = System.in.read();
            while (c != '-' && (c < '0' || c > '9'))
                c = System.in.read();
            if (c == '-')
                return -nextInt();
            int res = 0;
            while (c >= '0' && c <= '9') {
                res = res * 10 + c - '0';
                c = System.in.read();
            }
            return res;
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return -1;
    }
}
class Kruscal {
    int n;
    ArrayList<Edge> graph = new ArrayList<Edge>();
    public Kruscal(int n) {
        this.n = n;
    }
    public void addBidirectionalEdge(int u, int v, int cost) {
        // System.out.println(u + "," + v + "," + cost);
        graph.add(new Edge(cost, u, v));
    }
    public int minCost() {
        Collections.sort(graph);
        // System.out.println(graph);
        UnionFind uf = new UnionFind(n);
        int ans = 0;
        int connected = 1;
        for (int i = 0; i < graph.size(); i++) {
            Edge e = graph.get(i);
            if (!uf.isConnected(e.from, e.to)) {
                uf.union(e.from, e.to);
                connected++;
                ans = Math.max(ans, e.cost);
                if (connected == n) {
                    break;
                }
            }
            if (uf.isConnected(0, n - 1)) {
                return ans;
            }
        }
        return ans;
    }
    static class Edge implements Comparable<Edge> {
        int cost;
        int from;
        int to;
        public Edge(int cost, int from, int to) {
            this.cost = cost;
            this.from = from;
            this.to = to;
        }
        @Override
        public int compareTo(Edge o) {
            if (this.cost == o.cost) {
                return 0;
            } else if (this.cost > o.cost) {
                return 1;
            } else {
                return -1;
            }
        }
        public String toString() {
            return this.cost + "," + this.from + "," + this.to;
        }
    }
    static class UnionFind {
        private int[] data;
        public UnionFind(int size) {
            data = new int[size];
            Arrays.fill(data, -1);
        }
        public void union(int x, int y) {
            x = root(x);
            y = root(y);
            if (x != y) {
                if (data[y] < data[x]) {
                    int tmp = y;
                    y = x;
                    x = tmp;
                }
                data[x] += data[y];
                data[y] = x;
            }
        }
        public boolean isConnected(int x, int y) {
            return root(x) == root(y);
        }
        private int root(int x) {
            return data[x] < 0 ? x : (data[x] = root(data[x]));
        }
        public int size(int x) {
            return -data[root(x)];
        }
        public String toString() {
            return Arrays.toString(data);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0