Submission #2635232

---

Source Code Expand

import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def find_median(n, A, B, C):
    def slope(u):
        return -u[0] / u[1]

    lines = list(zip(A, B, C))
    lines.sort(key=slope)

    inf = 10 ** 20
    sa = -inf
    sb = inf
    n_steps = 100
    n_inversions_max = (n - 1) * n // 2
    for _ in range(n_steps):
        s = (sa + sb) / 2
        y = [(-a * s + c) / b for a, b, c, in lines]
        y.insert(0, 0)
        p = list(range(1, n + 1))
        p.sort(key=y.__getitem__, reverse=True)
        c = count_inversions(n, p)
        if c > n_inversions_max // 2:
            sb = s
        else:
            sa = s
    return s

def count_inversions(n, p):
    """Count the number of inversions
        t is the implicit data structure
        s[j] is the sum over ] j - j & -j, j]
    """
    res = 0
    s = [0] * (n + 1)
    for k in range(n):
        # sum over 1 .. t[p[k]]
        c = 0
        u = p[k]
        while u > 0:
            c += s[u]
            u -= u & -u
        # increment t[p[k]]
        u = p[k]
        while u <= n:
            s[u] += 1
            u += u & -u

        res += k - c
    return res


def count_inversions_slow_but_correct(n, p):
    """Count the number of inversions
        t is the implicit data structure
        s[j] is the sum over ] j - j & -j, j]
    """
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            res += p[i] > p[j]
    return res


def solve():
    n = read_int()
    a, b, c = zip(*[read_int_list() for i in range(n)])
    # find the median of x-coordinates
    x = find_median(n, a, b, c)
    y = find_median(n, b, a, c)
    return x, y


def main():
    res = solve()
    print(*res)


if __name__ == '__main__':
    main()

Submission Info

Judge Result