Eligible Segments (Codeforces 1584G)
Tags: Others, geometry

You are given $$$n$$$ distinct points $$$p_1, p_2, \ldots, p_n$$$ on the plane and a positive integer $$$R$$$. Find the number of pairs of indices $$$(i, j)$$$ such that $$$1 \le i < j \le n$$$, and for every possible $$$k$$$ ($$$1 \le k \le n$$$) the distance from the point $$$p_k$$$ to the segment between points $$$p_i$$$ and $$$p_j$$$ is at most $$$R$$$.

Input: The first line contains two integers $$$n$$$, $$$R$$$ ($$$1 \le n \le 3000$$$, $$$1 \le R \le 10^5$$$) — the number of points and the maximum distance between a point and a segment.Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$) that define the $$$i$$$-th point $$$p_i=(x_i, y_i)$$$. All points are distinct.It is guaranteed that the answer does not change if the parameter $$$R$$$ is changed by at most $$$10^{-2}$$$.

Output: Print the number of suitable pairs $$$(i, j)$$$.

Note: In the first example, the only pair of points $$$(-3, 0)$$$, $$$(3, 0)$$$ is suitable. The distance to the segment between these points from the points $$$(0, 1)$$$ and $$$(0, -1)$$$ is equal to $$$1$$$, which is less than $$$R=2$$$.In the second example, all possible pairs of points are eligible.

Sample Inputs:
4 2
0 1
0 -1
3 0
-3 0

3 3
1 -1
-1 -1
0 1

Sample Outputs:
1

3

Solution (Python):
from math import atan2, asin

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

def check(R, p, i, dp):
    (left, right) = (float('-inf'), float('inf'))
    angles = [0] * len(p)
    for j in range(len(p)):
        if j == i:
            continue
        curr = angles[j] = atan2(p[j][1] - p[i][1], p[j][0] - p[i][0])
        d = dist(p[i], p[j])
        if not d > R + EPS:
            continue
        delta = asin(R / d)
        (l, r) = (curr - delta, curr + delta)
        if l > right + EPS:
            (l, r) = (l - 2 * PI, r - 2 * PI)
        elif r < left - EPS:
            (l, r) = (l + 2 * PI, r + 2 * PI)
        (left, right) = (max(left, l), min(right, r))
        if left > right + EPS:
            return
    for j in range(len(p)):
        if j == i:
            continue
        curr = angles[j]
        if curr > right + EPS:
            curr -= 2 * PI
        elif curr < left - EPS:
            curr += 2 * PI
        if left - EPS <= curr <= right + EPS:
            dp[i][j] = 1

def solution():
    (n, R) = list(map(int, input().strip().split()))
    p = [list(map(int, input().strip().split())) for _ in range(n)]
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        check(R, p, i, dp)
    return sum((dp[i][j] and dp[j][i] for i in range(n) for j in range(i + 1, n)))
EPS = 1e-08
PI = 2 * atan2(1, 0)
print(solution())

Solution (Python):
from math import atan2, asin

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

def check(R, p, i, dp):
    (left, right) = (float('-inf'), float('inf'))
    for j in range(len(p)):
        if j == i:
            continue
        d = dist(p[i], p[j])
        if R >= d:
            continue
        delta = asin(R / d)
        angle = atan2(p[j][1] - p[i][1], p[j][0] - p[i][0])
        (l, r) = (angle - delta, angle + delta)
        if l > right:
            (l, r) = (l - 2 * PI, r - 2 * PI)
        elif r < left:
            (l, r) = (l + 2 * PI, r + 2 * PI)
        (left, right) = (max(left, l), min(right, r))
        if left > right:
            return
    for j in range(len(p)):
        if j == i:
            continue
        angle = atan2(p[j][1] - p[i][1], p[j][0] - p[i][0])
        if angle > right:
            angle -= 2 * PI
        elif angle < left:
            angle += 2 * PI
        if left <= angle <= right:
            dp[i][j] = 1

def solution():
    (n, R) = list(map(int, input().strip().split()))
    p = [list(map(int, input().strip().split())) for _ in range(n)]
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        check(R, p, i, dp)
    return sum((dp[i][j] and dp[j][i] for i in range(n) for j in range(i, n)))
PI = 2 * atan2(1, 0)
print(solution())

Solution (Python):
from math import atan2, asin

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

def check(R, p, i, dp):
    (left, right) = (float('-inf'), float('inf'))
    for j in range(len(p)):
        if j == i:
            continue
        d = dist(p[i], p[j])
        if not d > R + EPS:
            continue
        delta = asin(R / d)
        angle = atan2(p[j][1] - p[i][1], p[j][0] - p[i][0])
        (l, r) = (angle - delta, angle + delta)
        if l > right + EPS:
            (l, r) = (l - 2 * PI, r - 2 * PI)
        elif r < left - EPS:
            (l, r) = (l + 2 * PI, r + 2 * PI)
        (left, right) = (max(left, l), min(right, r))
        if left > right + EPS:
            return
    for j in range(len(p)):
        if j == i:
            continue
        angle = atan2(p[j][1] - p[i][1], p[j][0] - p[i][0])
        if angle > right + EPS:
            angle -= 2 * PI
        elif angle < left - EPS:
            angle += 2 * PI
        if left - EPS <= angle <= right + EPS:
            dp[i][j] = 1

def solution():
    (n, R) = list(map(int, input().strip().split()))
    p = [list(map(int, input().strip().split())) for _ in range(n)]
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        check(R, p, i, dp)
    return sum((dp[i][j] and dp[j][i] for i in range(n) for j in range(i, n)))
EPS = 1e-08
PI = 2 * atan2(1, 0)
print(solution())