am1x icon

pen001

am1x | PRO | 09/03/24 05:51:57 PM UTC (Edited) | 0 ⭐ | 577 👁️ | Never ⏰ | []
Python |

1.08 KB

|

Fixit

|

0 👍

/

0 👎

def main():
    n = int(input())
    assert 1 <= n <= 100000
    ps = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        assert abs(x) <= 1000000000
        assert abs(y) <= 1000
        ps[i] = (x, y)
    ps.sort()
    
    sy1 = 0
    sy2 = 0
    for p in ps:
        y = p[1]
        sy1 += y
        sy2 += y * y
    res = (n * sy2 - sy1 * sy1) / n
    resp = (ps[0][0] - 0.5, sy1 / n, sy1 / n)
    sy1l, sy1r = 0, sy1
    sy2l, sy2r = 0, sy2
    k = 0
    while True:
        x0 = ps[k][0]
        while k < n:
            x, y = ps[k]
            if x != x0:
                break
            k += 1
            sy1l += y
            sy1r -= y
            sy2l += y * y
            sy2r -= y * y 
        if n <= k:
            break
        tres = (k * sy2l - sy1l * sy1l) / k + ((n - k) * sy2r - sy1r * sy1r) / (n - k)
        tresp = (ps[k][0] - 0.5, sy1l / k, sy1r / (n - k))
        if tres < res:
            res = tres
            resp = tresp
    print(resp[1], resp[2], resp[0])
 
if __name__ == '__main__':
    main()

Comments