Problem p03585 (python)

Fixed submission:
import os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = int(inp[0])
    lim = (n * (n - 1) // 2 + 1) // 2
    aaa = inp[1::3]
    bbb = inp[2::3]
    ccc = inp[3::3]

    inclines_x = []
    inclines_y = []
    for i in range(n):
        inclines_x.append((aaa[i] / bbb[i], i))
        inclines_y.append((bbb[i] / aaa[i], i))
    inclines_x.sort()
    inclines_y.sort()
    incline_rank_x = np.zeros(n, dtype=np.int64)
    incline_rank_y = np.zeros(n, dtype=np.int64)
    for k in range(n):
        incline_rank_x[inclines_x[k][1]] = n - k
        incline_rank_y[inclines_y[k][1]] = n - k

    def check_x(m):
        yyy = []
        for i in range(n):
            yyy.append(((ccc[i] - aaa[i] * m) / bbb[i], i))
        yyy.sort()

        bit = np.zeros(n + 1, dtype=np.int64)
        intersection_left = 0
        for j in range(n):
            i = yyy[j][1]
            k = incline_rank_x[i]
            intersection_left += bit_sum(bit, k)
            bit_add(bit, n + 1, k, 1)

        return intersection_left >= lim

    def check_y(m):
        xxx = []
        for i in range(n):
            xxx.append(((ccc[i] - bbb[i] * m) / aaa[i], i))
        xxx.sort()

        bit = np.zeros(n + 1, dtype=np.int64)
        intersection_left = 0
        for j in range(n):
            i = xxx[j][1]
            k = incline_rank_y[i]
            intersection_left += bit_sum(bit, k)
            bit_add(bit, n + 1, k, 1)

        return intersection_left >= lim

    l = -2.0 * 10 ** 8
    r = 2.0 * 10 ** 8
    while r - l > 1e-9 and abs((r - l) / l if l != 0 else r) > 1e-9:
        m = (l + r) / 2
        if check_x(m):
            r = m
        else:
            l = m
    x = l

    l = -2.0 * 10 ** 8
    r = 2.0 * 10 ** 8
    while r - l > 1e-9 and abs((r - l) / l if l != 0 else r) > 1e-9:
        m = (l + r) / 2
        if check_y(m):
            r = m
        else:
            l = m
    y = l

    return x, y


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(f8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(f8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.buffer.read(), dtype=np.float64, sep=' ')
try:
    x, y = solve(inp)
    print(x, y)
except ZeroDivisionError:
    print('WA')
    exit()

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = int(inp[0])
    m = n * (n - 1) // 2
    aaa = inp[1::3]
    bbb = inp[2::3]
    ccc = inp[3::3]
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[(m - 1) // 2], intersections_y[(m - 1) // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(f8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(f8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.buffer.read(), dtype=np.float64, sep=' ')
try:
    x, y = solve(inp)
    print(x, y)
except ZeroDivisionError:
    print('WA')
    exit()

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = int(inp[0])
    m = n * (n - 1) // 2
    aaa = inp[1::3]
    bbb = inp[2::3]
    ccc = inp[3::3]
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[(m - 1) // 2], intersections_y[(m - 1) // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(f8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(f8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.buffer.read(), dtype=np.float64, sep=' ')
x, y = solve(inp)
print(x, y)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        if a * e - b * d == 0:
            print('WA')
            return c, f
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = int(inp[0])
    m = n * (n - 1) // 2
    aaa = inp[1::3]
    bbb = inp[2::3]
    ccc = inp[3::3]
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[(m - 1) // 2], intersections_y[(m - 1) // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(f8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(f8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.float64, sep=' ')
x, y = solve(inp)
print(x, y)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        if a * e - b * d == 0:
            print('WA')
            exit()
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = inp[0]
    m = n * (n - 1) // 2
    aaa = inp[1::3].astype(np.float64)
    bbb = inp[2::3].astype(np.float64)
    ccc = inp[3::3].astype(np.float64)
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[(m - 1) // 2], intersections_y[(m - 1) // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
x, y = solve(inp)
print(x, y)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        if a == 0:
            y = c / b
            x = (f - e * y) / d
            return x, y
        if d == 0:
            y = f / e
            x = (c - b * y) / a
            return x, y
        if b == 0:
            x = c / a
            y = (f - d * x) / e
            return x, y
        if e == 0:
            x = f / d
            y = (c - a * x) / b
            return x, y
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = inp[0]
    m = n * (n - 1) // 2
    aaa = inp[1::3].astype(np.float64)
    bbb = inp[2::3].astype(np.float64)
    ccc = inp[3::3].astype(np.float64)
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[(m - 1) // 2], intersections_y[(m - 1) // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
x, y = solve(inp)
print(x, y)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np


def solve(inp):
    def intersection(a, b, c, d, e, f):
        if a == 0:
            y = c / b
            x = (f - e * y) / d
            return x, y
        if d == 0:
            y = f / e
            x = (c - b * y) / a
            return x, y
        if b == 0:
            x = c / a
            y = (f - d * x) / e
            return x, y
        if e == 0:
            x = f / d
            y = (c - a * x) / b
            return x, y
        x = (c * e - b * f) / (a * e - b * d)
        y = (f - d * x) / e
        return x, y

    n = inp[0]
    m = n * (n - 1) // 2
    aaa = inp[1::3]
    bbb = inp[2::3]
    ccc = inp[3::3]
    intersections_x = np.zeros(m, dtype=np.float64)
    intersections_y = np.zeros(m, dtype=np.float64)
    k = 0
    for i in range(n - 1):
        a = aaa[i]
        b = bbb[i]
        c = ccc[i]
        for j in range(i + 1, n):
            d = aaa[j]
            e = bbb[j]
            f = ccc[j]
            x, y = intersection(a, b, c, d, e, f)
            intersections_x[k] = x
            intersections_y[k] = y
            k += 1
    intersections_x.sort()
    intersections_y.sort()

    return intersections_x[m // 2], intersections_y[m // 2]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
x, y = solve(inp)
print(x, y)