結果
| 問題 | No.96 圏外です。 |
| ユーザー |
 uwi
|
| 提出日時 | 2014-12-07 20:12:53 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,987 ms / 5,000 ms |
| コード長 | 8,458 bytes |
| コンパイル時間 | 3,081 ms |
| コンパイル使用メモリ | 92,396 KB |
| 実行使用メモリ | 66,744 KB |
| 最終ジャッジ日時 | 2024-12-24 07:52:31 |
| 合計ジャッジ時間 | 40,747 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
import java.awt.geom.Line2D;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;import java.util.InputMismatchException;public class Main {static InputStream is;static PrintWriter out;static String INPUT = "";static void solve(){int n = ni();if(n == 0){out.println(1);return;}int[][] co = new int[n][];long[] codes = new long[n];for(int i = 0;i < n;i++){co[i] = new int[]{ni(), ni()};codes[i] = co[i][0]+20000L<<48|co[i][1]+20000L<<32|i+1;}Arrays.sort(codes);int p = 0;for(int i = 0;i < n;i++){if(i == 0 || codes[i]>>>32 != codes[i-1]>>>32){codes[p++] = codes[i];}}codes = Arrays.copyOf(codes, p);DJSet ds = new DJSet(n);for(int i = 0;i < n;i++){int x = co[i][0], y = co[i][1];for(int j = -10;j <= 10;j++){for(int k = -10;k <= 10;k++){if(j*j+k*k <= 100){int dx = x + j, dy = y + k;long low = (long)dx+20000L<<48|dy+20000L<<32|0;int ind = Arrays.binarySearch(codes, low);ind = -ind-1;if(ind < codes.length && codes[ind]>>>32 == low>>>32){ds.union(((int)codes[ind])-1, i);}}}}}int[][] g = makeBuckets(ds);double max = 0;for(int[] row : g){int m = row.length;double[][] lco = new double[m][];for(int i = 0;i < m;i++){lco[i] = new double[]{co[row[i]][0], co[row[i]][1]};}double[][] hull = convexHull(lco);max = Math.max(max, findMostFarPair(hull) + 2);}out.printf("%.12f\n", max);}public static double findMostFarPair(double[][] co){int h = co.length;if(h <= 1)return 0.;int is = 0, js = 0;for(int j = 1;j < h;j++){if(co[j][1] > co[is][1])is = j;if(co[j][1] < co[js][1])js = j;}double max =(co[is][0]-co[js][0])*(co[is][0]-co[js][0])+(co[is][1]-co[js][1])*(co[is][1]-co[js][1]);int i, maxi, j, maxj;i = maxi = is;j = maxj = js;int ii = i+1, jj = j+1;if(ii >= h)ii -= h;if(jj >= h)jj -= h;int si = 0, sj = 0;do{double ax = co[ii][0]-co[i][0];double ay = co[ii][1]-co[i][1];double bx = co[jj][0]-co[j][0];double by = co[jj][1]-co[j][1];if(ax*by-ay*bx >= 0){j = jj;jj = j+1;if(jj >= h)jj -= h;sj++;}else{i = ii;ii = i+1;if(ii >= h)ii -= h;si++;}double nor =(co[i][0]-co[j][0])*(co[i][0]-co[j][0])+(co[i][1]-co[j][1])*(co[i][1]-co[j][1]);if(nor > max){max = nor;maxi = i;maxj = j;}}while(si <= h && sj <= h);return Math.sqrt(max);}public static double[][] convexHull(double[][] co){int n = co.length;if(n <= 1)return co;Arrays.sort(co, new Comparator<double[]>(){public int compare(double[] a, double[] b){if(a[0] - b[0] != 0)return (int)Math.signum(a[0] - b[0]);return (int)Math.signum(a[1] - b[1]);}});int[] inds = new int[n + 1];int p = 0;for(int i = 0;i < n;i++){if(p >= 1 && co[inds[p-1]][0] == co[i][0] && co[inds[p-1]][1] == co[i][1])continue;while(p >= 2 && Line2D.relativeCCW(co[inds[p-2]][0], co[inds[p-2]][1],co[inds[p-1]][0], co[inds[p-1]][1],co[i][0], co[i][1]) == 1)p--;inds[p++] = i;}int inf = p + 1;for(int i = n - 2;i >= 0;i--){if(co[inds[p-1]][0] == co[i][0] && co[inds[p-1]][1] == co[i][1])continue;while(p >= inf && Line2D.relativeCCW(co[inds[p-2]][0], co[inds[p-2]][1],co[inds[p-1]][0], co[inds[p-1]][1],co[i][0], co[i][1]) == 1)p--;inds[p++] = i;}double[][] ret = new double[p-1][];for(int i = 0;i < p-1;i++)ret[i] = co[inds[i]];return ret;}public static int[][] makeBuckets(DJSet ds){int n = ds.upper.length;int[] roots = new int[n];int[] where = new int[n];int p = 0;for(int i = 0;i < n;i++){if(ds.upper[i] < 0){roots[p++] = i;where[i] = p-1;}}int[][] bucket = new int[p][];for(int i = 0;i < p;i++){bucket[i] = new int[-ds.upper[roots[i]]];}int[] bp = new int[p];for(int i = 0;i < n;i++){int ind = where[ds.root(i)];bucket[ind][bp[ind]++] = i;}return bucket;}public static class DJSet {public int[] upper;public DJSet(int n) {upper = new int[n];Arrays.fill(upper, -1);}public int root(int x) {return upper[x] < 0 ? x : (upper[x] = root(upper[x]));}public boolean equiv(int x, int y) {return root(x) == root(y);}public boolean union(int x, int y) {x = root(x);y = root(y);if (x != y) {if (upper[y] < upper[x]) {int d = x;x = y;y = d;}upper[x] += upper[y];upper[y] = x;}return x == y;}public int count() {int ct = 0;for (int u : upper)if (u < 0)ct++;return ct;}}public static void main(String[] args) throws Exception{// int n = 120000, m = 99999;// Random gen = new Random();// StringBuilder sb = new StringBuilder();// sb.append(n + " ");// for (int i = 0; i < n; i++) {// sb.append(gen.nextInt(20000)-10000 + " ");// sb.append(gen.nextInt(20000)-10000 + " ");// }// INPUT = sb.toString();long S = System.currentTimeMillis();is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);solve();out.flush();long G = System.currentTimeMillis();tr(G-S+"ms");}private static boolean eof(){if(lenbuf == -1)return true;int lptr = ptrbuf;while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;try {is.mark(1000);while(true){int b = is.read();if(b == -1){is.reset();return true;}else if(!isSpaceChar(b)){is.reset();return false;}}} catch (IOException e) {return true;}}private static byte[] inbuf = new byte[1024];static int lenbuf = 0, ptrbuf = 0;private static int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private static double nd() { return Double.parseDouble(ns()); }private static char nc() { return (char)skip(); }private static String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private static char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private static char[][] nm(int n, int m){char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private static int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private static int ni(){int num = 0, b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }}