結果
問題 | No.94 圏外です。(EASY) |
ユーザー | scache |
提出日時 | 2014-12-08 03:47:17 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 252 ms / 5,000 ms |
コード長 | 1,981 bytes |
コンパイル時間 | 3,641 ms |
コンパイル使用メモリ | 74,524 KB |
実行使用メモリ | 59,508 KB |
最終ジャッジ日時 | 2023-09-08 14:18:51 |
合計ジャッジ時間 | 9,193 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
55,876 KB |
testcase_01 | AC | 126 ms
56,032 KB |
testcase_02 | AC | 129 ms
55,740 KB |
testcase_03 | AC | 125 ms
55,552 KB |
testcase_04 | AC | 149 ms
55,456 KB |
testcase_05 | AC | 194 ms
56,392 KB |
testcase_06 | AC | 201 ms
56,672 KB |
testcase_07 | AC | 210 ms
57,048 KB |
testcase_08 | AC | 226 ms
58,808 KB |
testcase_09 | AC | 252 ms
59,048 KB |
testcase_10 | AC | 250 ms
59,028 KB |
testcase_11 | AC | 238 ms
59,152 KB |
testcase_12 | AC | 245 ms
59,100 KB |
testcase_13 | AC | 245 ms
58,788 KB |
testcase_14 | AC | 251 ms
59,028 KB |
testcase_15 | AC | 249 ms
59,204 KB |
testcase_16 | AC | 252 ms
59,336 KB |
testcase_17 | AC | 240 ms
59,120 KB |
testcase_18 | AC | 245 ms
58,708 KB |
testcase_19 | AC | 251 ms
59,508 KB |
testcase_20 | AC | 132 ms
55,804 KB |
testcase_21 | AC | 125 ms
55,952 KB |
ソースコード
import java.util.ArrayList; import java.util.Scanner; public class Main94 { public static void main(String[] args) { Main94 p = new Main94(); } public Main94() { 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 < x.length; i++) { x[i] = sc.nextInt(); y[i] = sc.nextInt(); } solve(x, y); } public void solve(int[] x, int[] y) { if(x.length==0){ System.out.println(1); return; } uf(x.length); for(int i=0;i<x.length;i++){ for(int j=i+1;j<x.length;j++){ boolean isCross = isCrossCircle(x[i], y[i], 5, x[j], y[j], 5); if(isCross) unite(i, j); } } long dist = 0; for(int i=0;i<x.length;i++){ for(int j=i+1;j<x.length;j++){ if(same(i,j)) dist =Math.max(dist, (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); } } if(dist == 0) System.out.println(2); else System.out.println(Math.sqrt(dist)+2); } int[] par; int[] rank; private void uf(int n){ par = new int[n]; rank = new int[n]; for(int i=0;i<n;i++){ par[i] = i; rank[i] = 0; } } // 木の根を返す private int find(int x){ if(par[x] == x) return x; else return par[x] =find(par[x]); } // 併合 private void unite(int x, int y){ x = find(x); y = find(y); // すでに同じグループ if(x==y) return; if(rank[x]<rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x]==rank[y]) rank[x]++; } } // 同じグループなら真 private boolean same(int x, int y){ return find(x) == find(y); } // 円が交差しているなら真 private boolean isCrossCircle(long x1, long y1, long r1, long x2, long y2, long r2){ // 三平方の定理から求める long a = (x1-x2)*(x1-x2); long b = (y1-y2)*(y1-y2); long c = (r1+r2)*(r1+r2); return a+b <= c; } }