結果

問題 No.168 ものさし
ユーザー Grenache
提出日時 2016-05-25 20:07:35
言語 Java
(openjdk 23)
結果
AC  
実行時間 784 ms / 2,000 ms
コード長 2,349 bytes
コンパイル時間 3,985 ms
コンパイル使用メモリ 80,104 KB
実行使用メモリ 67,796 KB
最終ジャッジ日時 2024-12-24 07:13:47
合計ジャッジ時間 13,505 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

import java.util.*;
public class Main_yukicoder168 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        List<Tri> p = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long d = (long)(x[i] - x[j]) * (x[i] - x[j]) + (long)(y[i] - y[j]) * (y[i] - y[j]);
                p.add(new Tri(i, j, d));
            }
        }
        Collections.sort(p);
        UnionFind uf = new UnionFind(n);
        long min = Long.MAX_VALUE;
        for (Tri e : p) {
            uf.union(e.i, e.j);
            if (uf.same(0, n - 1)) {
                min = e.d;
                break;
            }
        }
        long l = 0;
        long r = 200_000_000;
        for (int i = 0; i < 100; i++) {
            long mid = l + (r - l) / 2;
            long tmp = (mid * 10) * (mid * 10) - min;
            if (tmp >= 0) {
                r = mid;
            } else {
                l = mid;
            }
        }
        System.out.println(r * 10);
        sc.close();
    }
    private static class Tri implements Comparable<Tri> {
        int i;
        int j;
        long d;
        Tri(int i, int j, long d) {
            this.i = i;
            this.j = j;
            this.d = d;
        }
        @Override
        public int compareTo(Tri o) {
            return Long.compare(this.d, o.d);
        }
    }
    @SuppressWarnings("unused")
    private static class UnionFind {
        int[] parent;
        int[] rank;
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
        int find(int x) {
            if (parent[x] == x) {
                return x;
            } else {
                return parent[x] = find(parent[x]);
            }
        }
        boolean same(int x, int y) {
            return find(x) == find(y);
        }
        void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                if (rank[x] > rank[y]) {
                    parent[y] = x;
                } else {
                    parent[x] = y;
                    if (rank[x] == rank[y]) {
                        rank[y]++;
                    }
                }
            }
            return;
        }
        // 異なる集合の数
        int count() {
            int ret = 0;
            for (int i = 0; i < parent.length; i++) {
                if (find(i) == i) {
                    ret++;
                }
            }
            return ret;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0