Rest In The Shades (Codeforces 1016E)
Tags: Others, geometry

There is a light source on the plane. This source is so small that it can be represented as point. The light source is moving from point $$$(a, s_y)$$$ to the $$$(b, s_y)$$$ $$$(s_y < 0)$$$ with speed equal to $$$1$$$ unit per second. The trajectory of this light source is a straight segment connecting these two points. There is also a fence on $$$OX$$$ axis represented as $$$n$$$ segments $$$(l_i, r_i)$$$ (so the actual coordinates of endpoints of each segment are $$$(l_i, 0)$$$ and $$$(r_i, 0)$$$). The point $$$(x, y)$$$ is in the shade if segment connecting $$$(x,y)$$$ and the current position of the light source intersects or touches with any segment of the fence.  You are given $$$q$$$ points. For each point calculate total time of this point being in the shade, while the light source is moving from $$$(a, s_y)$$$ to the $$$(b, s_y)$$$.

Input: First line contains three space separated integers $$$s_y$$$, $$$a$$$ and $$$b$$$ ($$$-10^9 \le s_y < 0$$$, $$$1 \le a < b \le 10^9$$$) — corresponding coordinates of the light source.Second line contains single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments in the fence.Next $$$n$$$ lines contain two integers per line: $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^9$$$, $$$r_{i - 1} < l_i$$$) — segments in the fence in increasing order. Segments don't intersect or touch each other.Next line contains single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — number of points to check.Next $$$q$$$ lines contain two integers per line: $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$) — points to process.

Output: Print $$$q$$$ lines. The $$$i$$$-th line should contain one real number — total time of the $$$i$$$-th point being in the shade, while the light source is moving from $$$(a, s_y)$$$ to the $$$(b, s_y)$$$. The answer is considered as correct if its absolute of relative error doesn't exceed $$$10^{-6}$$$.

Note:   The 1-st point is always in the shade;  the 2-nd point is in the shade while light source is moving from $$$(3, -3)$$$ to $$$(6, -3)$$$;  the 3-rd point is in the shade while light source is at point $$$(6, -3)$$$.  the 4-th point is in the shade while light source is moving from $$$(1, -3)$$$ to $$$(2.5, -3)$$$ and at point $$$(6, -3)$$$;  the 5-th point is in the shade while light source is moving from $$$(1, -3)$$$ to $$$(2.5, -3)$$$ and from $$$(5.5, -3)$$$ to $$$(6, -3)$$$; 

Sample Inputs:
-3 1 6
2
2 4
6 7
5
3 1
1 3
6 1
6 4
7 6

Sample Outputs:
5.000000000000000
3.000000000000000
0.000000000000000
1.500000000000000
2.000000000000000

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_search1(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok1(m):
            c2 = m
        else:
            c1 = m
    m = max(m - 1, 0)
    while not ok1(m):
        m += 1
    return m

def ok1(m):
    (l, _) = lr[m]
    l0 = s * (l - x) + l * y
    return True if a * y <= l0 else False

def binary_search2(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok2(m):
            c1 = m
        else:
            c2 = m
    m = min(m + 1, n + 1)
    while not ok2(m):
        m -= 1
    return m

def ok2(m):
    (_, r) = lr[m]
    r0 = s * (r - x) + r * y
    return True if b * y >= r0 else False
(sy, a, b) = map(int, input().split())
s = -sy
n = int(input())
inf = pow(10, 9) + 1
lr = [(-1, 0)] + [tuple(map(int, input().split())) for _ in range(n)] + [(inf, inf + 1)]
u = [0]
for (l, r) in lr:
    u.append(u[-1] + r - l)
q = int(input())
ans = []
for _ in range(q):
    (x, y) = map(int, input().split())
    l0 = binary_search1(0, n + 2)
    r0 = binary_search2(0, n + 2)
    if l0 == r0 + 2:
        ans0 = b - a
    else:
        ans0 = (u[r0 + 1] - u[l0]) / y * (y + s)
        l0 -= 1
        if l0:
            (_, r) = lr[l0]
            ans0 += max(a, s / y * (r - x) + r) - a
        r0 += 1
        if r0 ^ n + 1:
            (l, _) = lr[r0]
            ans0 += b - min(b, s / y * (l - x) + l)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        import math
        inf = math.inf

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

def main():
    (sy, a, b) = MII()
    n = II()
    ls = []
    rs = []
    for _ in range(n):
        (l, r) = MII()
        ls.append(l)
        rs.append(r)
    acc = [0] * (n + 1)
    for i in range(n):
        acc[i + 1] = acc[i] + rs[i] - ls[i]
    q = II()
    for _ in range(q):
        (x, y) = MII()
        tot_length = (b - a) * y / (y - sy)
        find_l = x + (a - x) * y / (y - sy)
        find_r = x + (b - x) * y / (y - sy)
        pl = bisect.bisect_left(rs, find_l)
        pr = bisect.bisect_left(ls, find_r) - 1
        if pr < pl:
            print(0)
        elif pr == pl:
            print((min(find_r, rs[pr]) - max(find_l, ls[pl])) / tot_length * (b - a))
        else:
            print((min(find_r, rs[pr]) - ls[pr] + rs[pl] - max(find_l, ls[pl]) + acc[pr] - acc[pl + 1]) / tot_length * (b - a))
    return
t = 1
for _ in range(t):
    main()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
(sy, a, b) = map(int, input().split())
seg = []
X = set()
n = int(input())
for _ in range(n):
    (x, y) = map(int, input().split())
    seg.append(x)
    seg.append(y)
    X.add(x)
    X.add(y)
q = int(input())
query = []

def cross(x0, y0, x1, y1):
    return x0 - (x1 - x0) / (y1 - y0) * y0
for _ in range(q):
    (x, y) = map(int, input().split())
    L = cross(a, sy, x, y)
    R = cross(b, sy, x, y)
    query.append((L, R))
    X.add(L)
    X.add(R)
X.add(0)
X = sorted(list(X))
m = len(X)
d = [X[i + 1] - X[i] for i in range(m - 1)]
c = [0]
tmp = 0
for i in range(1, m):
    if tmp < 2 * n and abs(X[i] - seg[tmp]) < 10 ** (-8):
        tmp += 1
    c.append(c[-1])
    if tmp % 2:
        c[-1] += d[i]
from bisect import bisect_left
ans = []
for (L, R) in query:
    l = bisect_left(X, L)
    r = bisect_left(X, R)
    res = c[r - 1] - c[l - 1]
    ans.append(res / (R - L) * (b - a))
print('\n'.join(map(str, ans)))