結果

問題 No.168 ものさし
ユーザー kenkooookenkoooo
提出日時 2015-03-20 00:59:38
言語 Java21
(openjdk 21)
結果
AC  
実行時間 531 ms / 2,000 ms
コード長 3,214 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 83,044 KB
実行使用メモリ 62,920 KB
最終ジャッジ日時 2024-06-06 14:50:42
合計ジャッジ時間 7,697 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 234 ms
47,592 KB
testcase_01 AC 47 ms
36,832 KB
testcase_02 AC 46 ms
37,020 KB
testcase_03 AC 47 ms
36,980 KB
testcase_04 AC 47 ms
36,736 KB
testcase_05 AC 46 ms
36,796 KB
testcase_06 AC 48 ms
36,836 KB
testcase_07 AC 47 ms
37,148 KB
testcase_08 AC 48 ms
36,652 KB
testcase_09 AC 66 ms
37,372 KB
testcase_10 AC 98 ms
39,744 KB
testcase_11 AC 202 ms
47,916 KB
testcase_12 AC 379 ms
54,864 KB
testcase_13 AC 455 ms
62,920 KB
testcase_14 AC 442 ms
62,648 KB
testcase_15 AC 47 ms
37,020 KB
testcase_16 AC 54 ms
37,084 KB
testcase_17 AC 74 ms
38,152 KB
testcase_18 AC 117 ms
40,548 KB
testcase_19 AC 529 ms
62,716 KB
testcase_20 AC 507 ms
62,736 KB
testcase_21 AC 530 ms
62,720 KB
testcase_22 AC 531 ms
62,696 KB
権限があれば一括ダウンロードができます

ソースコード

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 = (long) Math.sqrt(distSq);
				while (distSq > d * d) {
					d++;
				}

				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);
		}
	}
}
0