Submission #1258981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258981		aditya_k47	Mobile (BOI12_mobile)	Pypy 3	0 / 100	1101 ms	171920 KiB

mobile

from collections import deque
import math

def solve_d(x1, y1, x2, y2):
    return (x2**2 + y2**2 - x1**2 - y1**2) / (2 * (x2 - x1))

def dist(x, px, py):
    return math.sqrt((x - px)**2 + py**2)

n, L = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]

hull = deque()
for (x, y) in points:
    while len(hull) >= 2:
        x1, y1 = hull[-2]
        x2, y2 = hull[-1]
        cross = solve_d(x1, y1, x2, y2)
        cross2 = solve_d(x2, y2, x, y)
        if cross >= cross2:
            hull.pop()
        else:
            break
    hull.append((x, y))

ans = 0.0

ans = max(ans, min(dist(0, px, py) for (px, py) in hull))
ans = max(ans, min(dist(L, px, py) for (px, py) in hull))

for i in range(len(hull) - 1):
    x1, y1 = hull[i]
    x2, y2 = hull[i+1]
    xc = solve_d(x1, y1, x2, y2)
    if 0 <= xc <= L:
        d = dist(xc, x1, y1)  
        ans = max(ans, d)

print(f"{ans:.6f}")

Compilation message (stdout)

Compiling 'mobile.py'...

=======
  adding: __main__.pyc (deflated 43%)

=======

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5