Submission #3014988

---

Source Code Expand

class BIT
    def initialize(n)
        @n = n+1
        @dat = Array.new(@n+1, 0)
    end

    def sum(i)
        s = 0
        while i >= 0 do
            s += @dat[i]
            i = (i & (i + 1)) - 1
        end
        s
    end

    def add(i, x)
        while i <= @n do
            @dat[i] += x
            i |= i + 1
        end
    end
end

def inversion(arr)
    bit = BIT.new(arr.length)
    ret = 0
    arr.length.times do |i|
        ret += i - bit.sum(arr[i])
        bit.add(arr[i], 1)
    end
    ret
end

N = gets.to_i
abc = N.times.map{gets.split.map(&:to_i)}
abc.sort_by!{|arr| arr[0].to_f/arr[1]}
half = (N*(N-1)/2+1)/2

ub = 10.0**9
lb = -10.0**9
while ub-lb > 0.1**10
    mid = (ub+lb)/2
    order = N.times.sort_by{|i| (-abc[i][0]*mid+abc[i][2]).to_f/abc[i][1]}
    inv = inversion(order)
    if inv < half
        lb = mid
    else
        ub = mid
    end
end
x = ub

abc.sort_by!{|arr| arr[1].to_f/arr[0]}

ub = 10.0**9
lb = -10.0**9
while ub-lb > 0.1**10
    mid = (ub+lb)/2
    order = N.times.sort_by{|i| (-abc[i][1]*mid+abc[i][2]).to_f/abc[i][0]}
    inv = inversion(order)
    if inv < half
        lb = mid
    else
        ub = mid
    end
end
y = ub

puts [x, y].join(' ')

Submission Info

Judge Result