Submission #2113687


Source Code Expand

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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskE {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			int[] a = new int[n];
			int[] b = new int[n];
			int[] c = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = in.nextInt();
				b[i] = in.nextInt();
				c[i] = -in.nextInt();
			}
			double x = findX(n, a, b, c);
			double y = findX(n, b, a, c);
			out.printf("%.15f %.15f\n", x, y);
		}

		private double findX(int n, int[] a, int[] b, int[] c) {
			for (int i = 0; i < n; i++) {
				if (b[i] < 0 || b[i] == 0 && a[i] < 0) {
					a[i] = -a[i];
					b[i] = -b[i];
					c[i] = -c[i];
				}
			}
			final double BOUND = 1e9 + 100;
			double l = -BOUND;
			double r = +BOUND;
			long k = (long) n * (n - 1) / 2;
			long need = (k + 1) / 2;
			Integer[] p = new Integer[n];
			for (int i = 0; i < n; i++) {
				p[i] = i;
			}
			Arrays.sort(p, (u, v) -> (a[u] * b[v] - a[v] * b[u]));
			int[] tree = new int[n];
			Pair[] pairs = new Pair[n];
			for (int i = 0; i < n; i++) {
				pairs[i] = new Pair();
			}
			for (int step = 0; step < 100; step++) {
				double m = 0.5 * (l + r);
				Arrays.fill(tree, 0);
				for (int i = 0; i < n; i++) {
					pairs[i].a = -(a[p[i]] * m + c[p[i]]) / b[p[i]];
					pairs[i].b = i;
				}
				long inversions = 0;
				Arrays.sort(pairs, (u, v) -> Double.compare(u.a, v.a));
				for (int i = 0; i < n; i++) {
					inversions += sum(tree, pairs[i].b, n - 1);
					add(tree, pairs[i].b, 1);
				}
				if (inversions < need) {
					l = m;
				} else {
					r = m;
				}
			}
			return 0.5 * (l + r);
		}

		public void add(int[] tree, int pos, int val) {
			while (pos < tree.length) {
				tree[pos] += val;
				pos |= pos + 1;
			}
		}

		public long sum(int[] tree, int l, int r) {
			if (l > r) {
				return 0;
			}
			return sum(tree, r) - sum(tree, l - 1);
		}

		public long sum(int[] tree, int r) {
			long res = 0;
			while (r >= 0) {
				res += tree[r];
				r = (r & (r + 1)) - 1;
			}
			return res;
		}

		class Pair {
			double a;
			int b;

		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

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

	}
}

Submission Info

Submission Time
Task E - CARtesian Coodinate
User fetetriste
Language Java8 (OpenJDK 1.8.0)
Score 800
Code Size 3423 Byte
Status AC
Exec Time 3351 ms
Memory 54452 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 35
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 2973 ms 46224 KB
02.txt AC 3253 ms 51008 KB
03.txt AC 3078 ms 52924 KB
04.txt AC 3040 ms 46908 KB
05.txt AC 3031 ms 47196 KB
06.txt AC 3302 ms 46196 KB
07.txt AC 3351 ms 53268 KB
08.txt AC 3071 ms 47612 KB
09.txt AC 3074 ms 46528 KB
10.txt AC 3327 ms 47648 KB
11.txt AC 3052 ms 47668 KB
12.txt AC 3147 ms 44560 KB
13.txt AC 3267 ms 46056 KB
14.txt AC 3086 ms 45888 KB
15.txt AC 3288 ms 47876 KB
16.txt AC 3282 ms 47896 KB
17.txt AC 3031 ms 49052 KB
18.txt AC 3247 ms 47312 KB
19.txt AC 3329 ms 46224 KB
20.txt AC 3050 ms 54452 KB
21.txt AC 1046 ms 47248 KB
22.txt AC 1046 ms 43948 KB
23.txt AC 3159 ms 52332 KB
24.txt AC 3183 ms 47268 KB
25.txt AC 3203 ms 45904 KB
26.txt AC 3137 ms 44800 KB
27.txt AC 162 ms 24660 KB
28.txt AC 157 ms 24660 KB
29.txt AC 157 ms 26580 KB
30.txt AC 163 ms 26324 KB
31.txt AC 155 ms 24916 KB
32.txt AC 156 ms 25548 KB
s1.txt AC 163 ms 25676 KB
s2.txt AC 159 ms 25300 KB
s3.txt AC 165 ms 23892 KB