Submission #2113679


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 = 1e8 + 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 0
Code Size 3423 Byte
Status WA
Exec Time 3476 ms
Memory 55148 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 34
WA × 1
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 3178 ms 48428 KB
02.txt AC 3310 ms 47764 KB
03.txt AC 3230 ms 47108 KB
04.txt AC 3149 ms 49544 KB
05.txt AC 3168 ms 48536 KB
06.txt AC 3228 ms 53152 KB
07.txt AC 3445 ms 52640 KB
08.txt AC 3167 ms 51092 KB
09.txt AC 3145 ms 49088 KB
10.txt AC 3175 ms 47884 KB
11.txt AC 3312 ms 49384 KB
12.txt AC 3229 ms 47908 KB
13.txt AC 3391 ms 46376 KB
14.txt AC 3204 ms 51948 KB
15.txt AC 3169 ms 55148 KB
16.txt AC 3100 ms 45656 KB
17.txt AC 3361 ms 45312 KB
18.txt AC 3279 ms 44844 KB
19.txt AC 3378 ms 46088 KB
20.txt AC 3476 ms 45932 KB
21.txt AC 1149 ms 45420 KB
22.txt AC 1060 ms 41940 KB
23.txt AC 3251 ms 45608 KB
24.txt AC 3194 ms 44656 KB
25.txt AC 3313 ms 44832 KB
26.txt AC 3224 ms 54872 KB
27.txt WA 164 ms 25936 KB
28.txt AC 158 ms 26580 KB
29.txt AC 161 ms 28500 KB
30.txt AC 162 ms 24660 KB
31.txt AC 163 ms 26708 KB
32.txt AC 167 ms 22484 KB
s1.txt AC 162 ms 24404 KB
s2.txt AC 160 ms 26580 KB
s3.txt AC 154 ms 24276 KB