#82748 (Java21) No.96 圏外です。

提出ソース
結果

問題	No.96 圏外です。
ユーザー	atn112323
提出日時	2016-03-22 15:33:28
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,162 ms / 5,000 ms
コード長	17,430 bytes
コンパイル時間	3,407 ms
コンパイル使用メモリ	92,676 KB
実行使用メモリ	167,168 KB
最終ジャッジ日時	2024-06-06 16:19:42
合計ジャッジ時間	22,539 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	268 ms 120,692 KB
testcase_01	AC	268 ms 120,784 KB
testcase_02	AC	266 ms 120,312 KB
testcase_03	AC	58 ms 36,872 KB
testcase_04	AC	339 ms 118,592 KB
testcase_05	AC	375 ms 115,720 KB
testcase_06	AC	379 ms 109,984 KB
testcase_07	AC	334 ms 108,872 KB
testcase_08	AC	421 ms 122,692 KB
testcase_09	AC	482 ms 112,648 KB
testcase_10	AC	569 ms 129,248 KB
testcase_11	AC	518 ms 118,472 KB
testcase_12	AC	570 ms 122,968 KB
testcase_13	AC	636 ms 126,240 KB
testcase_14	AC	673 ms 130,072 KB
testcase_15	AC	896 ms 132,316 KB
testcase_16	AC	967 ms 167,168 KB
testcase_17	AC	803 ms 149,932 KB
testcase_18	AC	947 ms 159,428 KB
testcase_19	AC	946 ms 147,204 KB
testcase_20	AC	1,080 ms 137,424 KB
testcase_21	AC	1,008 ms 134,276 KB
testcase_22	AC	1,142 ms 160,072 KB
testcase_23	AC	1,162 ms 160,000 KB
testcase_24	AC	267 ms 120,736 KB
testcase_25	AC	701 ms 137,204 KB
testcase_26	AC	797 ms 146,212 KB
testcase_27	AC	719 ms 140,316 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Main {

	/**
	 * This class represents a problem setting.
	 */
	class Problem implements IProblem {

		int N;
		int[][] XY;
		
		@Override
		public void set(ProblemReader reader) throws IOException {
			N = reader.nextInt();
			XY = reader.nextIntArray2(N);
		}
		
		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(StringUtils.toString(N) + "\n");
			sb.append(StringUtils.toString(XY));
			return sb.toString();
		}
	}
	
	/**
	 * Solver for the problem.
	 * It's the most important part of codes in this file.
	 */
	class Solver implements IProblemSolver<Problem> {

		int N;
		int[][] XY;
		
		@Override
		public String solve(Problem problem) {
			N = problem.N;
			XY = problem.XY;
			return StringUtils.toString(solve());
		}
		
		private double solve() {
			if (N == 0) {
				return 1.0;
			}
			UnionFindTree uft = new UnionFindTree(N);
			Cell[][] cells = new Cell[4005][4005];
			for (int i = 0; i < N; i++) {
				XY[i][0] += 10000;
				XY[i][1] += 10000;
				int cx = XY[i][0] / 5, cy = XY[i][1] / 5;
				for (int cxx = cx - 2; cxx <= cx + 2; cxx++) {
					for (int cyy = cy - 2; cyy <= cy + 2; cyy++) {
						if (0 <= cxx && 0 <= cyy && cells[cxx][cyy] != null) {
							for (int id : cells[cxx][cyy].ids) {
								if (dist2(i, id) <= 100) {
									uft.unite(i, id);
								}
							}
						}
					}
				}
				if (cells[cx][cy] == null) {
					cells[cx][cy] = new Cell();
				}
				cells[cx][cy].ids.add(i);
			}
			
			Ids[] ids = new Ids[N];
			for (int i = 0; i < N; i++) {
				int x = uft.find(i);
				if (ids[x] == null) {
					ids[x] = new Ids();
				}
				ids[x].ids.add(i);
			}
			
			double max = 0.0;
			for (int i = 0; i < N; i++) {
				if (ids[i] != null) {
					max = Math.max(max, longest(ids[i].ids));
				}
			}
			return max + 2.0;
		}
		
		private int dist2(int idx1, int idx2) {
			int dx = XY[idx1][0] - XY[idx2][0];
			int dy = XY[idx1][1] - XY[idx2][1];
			return dx * dx + dy * dy;
		}
		
		private int vc(Point p1, Point p2, Point p3) {
			int x1 = p3.x - p1.x, y1 = p3.y - p1.y;
			int x2 = p2.x - p1.x, y2 = p2.y - p1.y;
			return y2 * x1 - x2 * y1;
		}
		
		private int dist2(Point p1, Point p2) {
			int dx = p1.x - p2.x, dy = p1.y - p2.y;
			return dx * dx + dy * dy;
		}
		
		private double longest(List<Integer> ids) {
			Point[] points = new Point[ids.size()];
			for (int i = 0; i < ids.size(); i++) {
				points[i] = new Point(XY[ids.get(i)][0], XY[ids.get(i)][1]);
			}
			Arrays.sort(points);
			List<Point> ps = new ArrayList<>();
			for (Point p : points) {
				while (ps.size() >= 2 && vc(ps.get(ps.size() - 2), ps.get(ps.size() - 1), p) <= 0) {
					ps.remove(ps.size() - 1);
				}
				ps.add(p);
			}
			int n = ps.size();
			for (int i = points.length - 2; i >= 0; i--) {
				Point p = points[i];
				while (ps.size() > n && vc(ps.get(ps.size() - 2), ps.get(ps.size() - 1), p) <= 0) {
					ps.remove(ps.size() - 1);
				}
				ps.add(p);
			}
			ps.remove(ps.size() - 1);
			
			double max = 0.0;
			int idx = 0;
			for (int i = 0; i < ps.size() && idx < ps.size(); i++) {
				Point p1 = ps.get(i);
				int dist2 = dist2(p1, ps.get(idx));
				for (;;) {
					int d2 = dist2(p1, ps.get((idx + 1) % ps.size()));
					if (d2 > dist2) {
						dist2 = d2;
						idx++;
					} else {
						break;
					}
				}
				max = Math.max(max, Math.sqrt(dist2));
			}
			return max;
		}
		
		class Cell {
			
			List<Integer> ids = new ArrayList<>();
		}
		
		class Point implements Comparable<Point> {
			
			int x, y;
			
			Point(int x, int y) {
				this.x = x;
				this.y = y;
			}
			
			@Override
			public int compareTo(Point point) {
				if (x != point.x) {
					return x - point.x;
				} else {
					return y - point.y;
				}
			}
		}
		
		class Ids {
			
			List<Integer> ids = new ArrayList<>();
		}
		
		class UnionFindTree {

			private int[] parent;
			private int[] rank;

			public UnionFindTree(int size) {
				parent = new int[size];
				rank = new int[size];
				init();
			}

			public void init() {
				for (int i=0; i<parent.length; i++) {
					parent[i] = i;
					rank[i] = 0;
				}
			}

			public int find(int x) {
				if (parent[x] == x) {
					return x;
				} else {
					return parent[x] = find(parent[x]);
				}
			}

			public void unite(int x, int y) {
				x = find(x);
				y = find(y);
				if (x==y) {
					return;
				}
				if (rank[x] < rank[y]) {
					parent[x] = y;
				} else {
					parent[y] = x;
					if (rank[x] == rank[y]) {
						rank[x]++;
					}
				}
			}

			public boolean same(int x, int y) {
				return find(x) == find(y);
			}
		}
	}
	
	/**
	 * This class is a solver to confirm the main solver.
	 * This solver often works only for a problem with a small number setting.
	 */
	class Solver2 implements IProblemSolver<Problem> {

		@Override
		public String solve(Problem problem) {
			int N = problem.N;
			int[][] XY = problem.XY;
			return StringUtils.toString(solve(N, XY));
		}
		
		private double solve(int N, int[][] XY) {
			if (N == 0) {
				return 1.0;
			}
			UnionFindTree uft = new UnionFindTree(N);
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					int d2 = (XY[i][0] - XY[j][0]) * (XY[i][0] - XY[j][0]) + (XY[i][1] - XY[j][1]) * (XY[i][1] - XY[j][1]);
					if (d2 <= 10 * 10) {
						uft.unite(i, j);
					}
				}
			}
			int max = 0;
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					if (uft.same(i, j)) {
						int d2 = (XY[i][0] - XY[j][0]) * (XY[i][0] - XY[j][0]) + (XY[i][1] - XY[j][1]) * (XY[i][1] - XY[j][1]);
						max = Math.max(max, d2);
					}
				}
			}
			return Math.sqrt(max) + 2;
		}
		
		class UnionFindTree {

			private int[] parent;
			private int[] rank;

			UnionFindTree(int size) {
				parent = new int[size];
				rank = new int[size];
				init();
			}

			void init() {
				for (int i=0; i<parent.length; i++) {
					parent[i] = i;
					rank[i] = 0;
				}
			}

			int find(int x) {
				if (parent[x] == x) {
					return x;
				} else {
					return parent[x] = find(parent[x]);
				}
			}

			void unite(int x, int y) {
				x = find(x);
				y = find(y);
				if (x==y) {
					return;
				}
				if (rank[x] < rank[y]) {
					parent[x] = y;
				} else {
					parent[y] = x;
					if (rank[x] == rank[y]) {
						rank[x]++;
					}
				}
			}

			boolean same(int x, int y) {
				return find(x) == find(y);
			}
		}
	}
	
	class Factory implements IProblemFactory<Problem> {

		@Override
		public Problem newProblem() {
			int N = 10000;
			int[][] xys = new int[N][2];
			int idx = 0;
			for (int x = 0; x < 100; x++) {
				for (int y = 0; y < 100; y++) {
					xys[idx++] = new int[]{x, y};
				}
			}
			Random rng = new Random();
			for (int i = 0; i < N; i++) {
				int rnd = rng.nextInt(N - i) + i;
				int[] tmp = xys[i]; xys[i] = xys[rnd]; xys[rnd] = tmp;
			}
			Problem problem = new Problem();
			problem.N = N;
			problem.XY = xys;
			return problem;
		}

		@Override
		public Problem newProblem(ProblemReader reader) throws IOException {
			Problem problem = new Problem();
			problem.set(reader);
			return problem;
		}
	}
	
	class ResultComparator implements IResultComparator {
		
		@Override
		public boolean same(String res1, String res2) {
			return res1.equals(res2);
		}
	}
	
	ProblemProcessor<Problem> processor;
	
	Main() {
		Init();
	}
	
	void Init() {
		ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();
		
		config.factory = new Factory();
		config.solver = new Solver();
		config.solver2 = new Solver2();
		config.comparator = new ResultComparator();
		
		processor = new ProblemProcessor<Problem>(config);
	}
	
	void process(String mode) throws IOException {
		processor.process(mode);
	}
	
	public static void main(String args[]) throws IOException {
		// "create", "debug", and "solve"
		String mode = "solve";
		new Main().process(mode);
	}
	
/*
	Common library
*/
	
	interface IProblem {
		
		abstract void set(ProblemReader reader) throws IOException;
	}
	
	interface IProblemFactory<P extends IProblem> {
		
		abstract P newProblem();
		abstract P newProblem(ProblemReader reader) throws IOException;
	}
	
	interface IProblemSolver<P extends IProblem> {
		
		abstract String solve(P problem);
	}
	
	interface IResultComparator {
		
		abstract boolean same(String res1, String res2);
	}
	
	class ProblemReader {
		
		BufferedReader br = null;
		
		ProblemReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		int nextInt() throws IOException {
			return StringUtils.toInt(br.readLine());
		}
		
		long nextLong() throws IOException {
			return StringUtils.toLong(br.readLine());
		}
		
		double nextDouble() throws IOException {
			return StringUtils.toDouble(br.readLine());
		}
		
		String nextString() throws IOException {
			return br.readLine();
		}
		
		int[] nextIntArray() throws IOException {
			return StringUtils.toIntArray(br.readLine());
		}
		
		long[] nextLongArray() throws IOException {
			return StringUtils.toLongArray(br.readLine());
		}
		
		double[] nextDoubleArray() throws IOException {
			return StringUtils.toDoubleArray(br.readLine());
		}
		
		String[] nextStringArray() throws IOException {
			return StringUtils.toStringArray(br.readLine());
		}
		
		int[] nextIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long[] nextLongArray(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextLong();
			}
			return a;
		}
		
		double[] nextDoubleArray(int n) throws IOException {
			double[] a = new double[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextDouble();
			}
			return a;
		}
		
		String[] nextStringArray(int n) throws IOException {
			String[] strs = new String[n];
			for (int i = 0; i < n; i++) {
				strs[i] = nextString();
			}
			return strs;
		}
		
		int[][] nextIntArray2(int n) throws IOException {
			int[][] a = new int[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextIntArray();
			}
			return a;
		}
		
		long[][] nextLongArray2(int n) throws IOException {
			long[][] a = new long[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextLongArray();
			}
			return a;
		}
		
		double[][] nextDoubleArray2(int n) throws IOException {
			double[][] a = new double[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextDoubleArray();
			}
			return a;
		}
		
		String[][] nextStringArray2(int n) throws IOException {
			String[][] strs = new String[n][];
			for (int i = 0; i < n; i++) {
				strs[i] = nextStringArray();
			}
			return strs;
		}
		
		void close() throws IOException {
			if (br != null) {
				br.close();
			}
		}
	}
	
	class ProblemCreator<P extends IProblem> {
		
		IProblemFactory<P> factory;
		
		ProblemCreator(IProblemFactory<P> factory) {
			this.factory = factory;
		}
		
		void create() throws FileNotFoundException {
			P problem = factory.newProblem();
			System.out.println(problem.toString());
		}
	}
	
	class ProblemSolverComparator<P extends IProblem> {
		
		IProblemFactory<P> factory;
		IProblemSolver<P> solver1, solver2;
		IResultComparator comparator;
		
		ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2, IResultComparator comparator) {
			this.factory = factory;
			this.solver1 = solver1;
			this.solver2 = solver2;
			this.comparator = comparator;
		}
		
		void compare() throws IOException {
			ProblemReader reader = null;
			try {
				reader = new ProblemReader();
				P problem = factory.newProblem(reader);
				String res1 = solver1.solve(problem);
				String res2 = solver2.solve(problem);
				if (comparator.same(res1, res2)) {
					System.out.println(res1);
				} else {
					System.err.println(res1 + " " + res2);
				}
			} finally {
				if (reader != null) {
					reader.close();
				}
			}
		}
	}
	
	class ProblemAnswerer<P extends IProblem> {
		
		IProblemFactory<P> factory;
		IProblemSolver<P> solver;
		
		ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {
			this.factory = factory;
			this.solver = solver;
		}
		
		void answer() throws IOException {
			ProblemReader reader = null;
			try {
				reader = new ProblemReader();
				P problem = factory.newProblem(reader);
				String res = solver.solve(problem);
				System.out.println(res);
			} finally {
				if (reader != null) {
					reader.close();
				}
			}
		}
	}
	
	class ProblemProcessorConfig<P extends IProblem> {
		
		IProblemFactory<P> factory;
		
		IProblemSolver<P> solver, solver2;
		
		IResultComparator comparator;
	}
	
	class ProblemProcessor<P extends IProblem> {
		
		ProblemProcessorConfig<P> config;
		
		ProblemCreator<P> creator;
		ProblemSolverComparator<P> comparator;
		ProblemAnswerer<P> answerer;
		
		ProblemProcessor(ProblemProcessorConfig<P> config) {
			this.config = config;
			creator = new ProblemCreator<P>(config.factory);
			comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2, config.comparator);
			answerer = new ProblemAnswerer<P>(config.factory, config.solver);
		}
		
		void process(String mode) throws IOException {
			switch (mode) {
			case "create":
				creator.create();
				break;
			case "debug":
				comparator.compare();
				break;
			case "solve":
				answerer.answer();
				break;
			}
		}
	}
	
	static class StringUtils {
		
		static String toString(int a) {
			return String.valueOf(a);
		}
		
		static String toString(long a) {
			return String.valueOf(a);
		}
		
		static String toString(double a) {
			return String.valueOf(a);
		}
		
		static String toString(String str) {
			return str;
		}
		
		static String toString(int[] a, String delimiter) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + delimiter);
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(long[] a, String delimiter) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + delimiter);
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(double[] a, String delimiter) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + delimiter);
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(String[] strs, String delimiter) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < strs.length; i++) {
				if (i < strs.length - 1) {
					sb.append(strs[i] + delimiter);
				} else {
					sb.append(strs[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(int[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(long[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(double[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(String[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static int toInt(String s) {
			return Integer.parseInt(s);
		}
		
		static long toLong(String s) {
			return Long.parseLong(s);
		}
		
		static double toDouble(String s) {
			return Double.parseDouble(s);
		}
		
		static int[] toIntArray(String s) {
			String[] tokens = s.split(" ");
			int[] a = new int[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Integer.parseInt(tokens[i]);
			}
			return a;
		}
		
		static long[] toLongArray(String s) {
			String[] tokens = s.split(" ");
			long[] a = new long[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Long.parseLong(tokens[i]);
			}
			return a;
		}
		
		static double[] toDoubleArray(String s) {
			String[] tokens = s.split(" ");
			double[] a = new double[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Double.parseDouble(tokens[i]);
			}
			return a;
		}
		
		static String[] toStringArray(String s) {
			return s.split(" ");
		}
	}
}
yukicoder

結果

テストケース

ソースコード
