Submission #623041

#	Time	Username	Problem	Language	Result	Execution time	Memory
623041		54skyxenon	Mobile (BOI12_mobile)	Cpython 3	25 / 100	1097 ms	77748 KiB

mobile

# https://oj.uz/problem/view/BOI12_mobile

EPS = 0.00001

n, l = map(int, input().split())

def dist(c1, c2):
    return ((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2) ** 0.5

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

def merge(intervals):
    new_intervals = []
    
    for start, end in sorted(intervals):
        if not new_intervals or new_intervals[-1][1] < start:
            new_intervals.append([start, end])
        else:
            new_intervals[-1][1] = max(new_intervals[-1][1], end)
    
    return new_intervals

def bs(lo, hi):
    def ok(radius):
        intervals = []

        for x1, y1 in coordinates:
            term = (radius ** 2) - (y1 ** 2)
            if term >= 0:
                term_sqrt = term ** 0.5
                intervals.append((x1 - term_sqrt, x1 + term_sqrt))
        
        intervals = merge([(0, 0)] + intervals + [(l, l)])
        
        for i in range(len(intervals) - 1):
            midpt = (intervals[i][1] + intervals[i + 1][0]) / 2
            if 0 <= midpt <= l:
                return True

        return False

    while lo + EPS < hi:
        mid = (lo + hi) / 2

        if not ok(mid):
            hi = mid
        else:
            lo = mid

    return lo

print(bs(0, l))

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 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