Submission #835847

#	Time	Username	Problem	Language	Result	Execution time	Memory
835847		iamjiamingliu	Mobile (BOI12_mobile)	Cpython 3	0 / 100	1077 ms	131072 KiB

mobile

import sys
import math

towers_cnt, line_len = map(int, sys.stdin.readline().strip().split())
towers = [tuple(map(int, sys.stdin.readline().strip().split())) for _ in range(towers_cnt)]

def can_cover_whole_line(radius: float) -> bool:
    curr = 0
    for x, y in towers:
        delta = math.sqrt(radius ** 2 - y ** 2)
        a, b = x - delta, x + delta
        if a <= curr:   curr = max(curr, b)
    return curr >= line_len
    # total_dist = 0
    # for x, height in towers:
    #     if height > radius:     continue
    #     dist = math.sqrt(radius ** 2 - height ** 2)
    #     if x - dist <= total_dist <= x + dist:
    #         total_dist = x + dist
    # return total_dist >= line_len

l, r = 0, 1.5e9
while not math.isclose(l, r):
    mid = (l + r) / 2
    if can_cover_whole_line(radius=mid):
        r = mid
    else:
        l = mid

print(l)

• 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