Submission #3767743


Source Code Expand

Copy
import static java.lang.Math.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		int n;
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			n = in.nextInt();
			long[] x = new long[n], y = new long[n];
			long[] u = new long[n], v = new long[n];
			for (int i = 0; i < n; i++) {
				x[i] = in.nextLong();
				y[i] = in.nextLong();
				u[i] = x[i] + y[i];
				v[i] = x[i] - y[i];
			}

			Arrays.sort(u);
			Arrays.sort(v);

			long d = max(u[n-1]-u[0], v[n-1]-v[0]);

			List<P> list = new ArrayList<>();
			list.add(new P(u[0]+d/2, v[0]+d/2));
			list.add(new P(u[0]+d/2, v[n-1]-d/2));
			list.add(new P(u[n-1]-d/2, v[0]+d/2));
			list.add(new P(u[n-1]-d/2, v[n-1]-d/2));

			for (P p : list) {

				long px = (p.first + p.second) / 2;
				long py = (p.first - p.second) / 2;

				if (check(px, py, x, y)) {
					out.printf("%d %d\n", px, py);
					return;
				}
			}
		}

		boolean check(long px, long py, long[] x, long[] y) {

			long d = abs(px - x[0]) + abs(py - y[0]);
			for (int i = 0; i < n; i++) {
				if (abs(px - x[i]) + abs(py - y[i]) == d) {
					continue;
				}
				return false;
			}

			return true;
		}
	}

	static class P {
		long first, second;

		public P(long first, long second) {
			super();
			this.first = first;
			this.second = second;
		}

		@Override
		public String toString() {
			return "P [first=" + first + ", second=" + second + "]";
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public int[] nextIntArray1Index(int n) {
			int[] res = new int[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public long[] nextLongArray1Index(int n) {
			long[] res = new long[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextLong();
			}
			return res;
		}

		public double[] nextDoubleArray(int n) {
			double[] res = new double[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}

Submission Info

Submission Time
Task B - 同一円周上
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 4292 Byte
Status
Exec Time 270 ms
Memory 45452 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 100 / 100 sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt
Case Name Status Exec Time Memory
sample_01.txt 76 ms 20180 KB
sample_02.txt 77 ms 18004 KB
subtask1_01.txt 76 ms 22996 KB
subtask1_02.txt 77 ms 18644 KB
subtask1_03.txt 77 ms 20180 KB
subtask1_04.txt 77 ms 18004 KB
subtask1_05.txt 78 ms 20820 KB
subtask1_06.txt 78 ms 20436 KB
subtask1_07.txt 76 ms 18260 KB
subtask1_08.txt 77 ms 21456 KB
subtask1_09.txt 76 ms 19796 KB
subtask1_10.txt 77 ms 20180 KB
subtask1_11.txt 251 ms 43044 KB
subtask1_12.txt 270 ms 45004 KB
subtask1_13.txt 156 ms 31564 KB
subtask1_14.txt 226 ms 40908 KB
subtask1_15.txt 203 ms 36416 KB
subtask1_16.txt 262 ms 45452 KB
subtask1_17.txt 156 ms 25772 KB
subtask1_18.txt 162 ms 25324 KB
subtask1_19.txt 223 ms 40468 KB
subtask1_20.txt 270 ms 39536 KB
subtask1_21.txt 167 ms 30792 KB
subtask1_22.txt 193 ms 30984 KB
subtask1_23.txt 148 ms 25328 KB
subtask1_24.txt 178 ms 33000 KB
subtask1_25.txt 261 ms 40864 KB
subtask1_26.txt 236 ms 42892 KB
subtask1_27.txt 240 ms 42340 KB
subtask1_28.txt 126 ms 23508 KB
subtask1_29.txt 264 ms 44972 KB
subtask1_30.txt 243 ms 41756 KB
subtask1_31.txt 202 ms 35176 KB
subtask1_32.txt 139 ms 25428 KB
subtask1_33.txt 93 ms 19156 KB
subtask1_34.txt 260 ms 40980 KB
subtask1_35.txt 222 ms 39824 KB
subtask1_36.txt 206 ms 36216 KB
subtask1_37.txt 256 ms 43184 KB
subtask1_38.txt 196 ms 35288 KB
subtask1_39.txt 264 ms 37396 KB
subtask1_40.txt 253 ms 40828 KB
subtask1_41.txt 147 ms 24532 KB
subtask1_42.txt 215 ms 42060 KB
subtask1_43.txt 207 ms 36728 KB
subtask1_44.txt 235 ms 44764 KB
subtask1_45.txt 242 ms 44748 KB
subtask1_46.txt 261 ms 42892 KB
subtask1_47.txt 78 ms 21588 KB