Submission #1258982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258982		aditya_k47	Mobile (BOI12_mobile)	Pypy 3	0 / 100	618 ms	141924 KiB

mobile

from collections import deque
import math

def solve_d(x1, y1, x2, y2):
    # x coordinate where distances to (x1,y1) and (x2,y2) are equal
    return (x2**2 + y2**2 - x1**2 - y1**2) / (2 * (x2 - x1))

n, l = map(int, input().split())
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

points.sort()
ans = 0.0

dq = deque()
dq.append(points[0])

# check at x=0
ans = max(ans, min(math.sqrt((0 - px)**2 + py**2) for px, py in points))

for i in range(1, n):
    if dq[-1][0] == points[i][0]:
        continue
    # compute intersection
    x_cross = solve_d(dq[-1][0], dq[-1][1], points[i][0], points[i][1])
    if 0 <= x_cross <= l:
        d = math.sqrt((x_cross - dq[-1][0])**2 + dq[-1][1]**2)
        ans = max(ans, d)
    dq.pop()
    dq.append(points[i])

# check at x=l
ans = max(ans, min(math.sqrt((l - px)**2 + py**2) for px, py in points))

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

Compilation message (stdout)

Compiling 'mobile.py'...

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

=======

• 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