Технокубок 2022 - Отборочный Раунд 2 |
---|
Закончено |
Вам даны $$$n$$$ различных точек $$$p_1, p_2, \ldots, p_n$$$ на плоскости, а также положительное целое число $$$R$$$.
Найдите количество пар индексов $$$(i, j)$$$ таких, что $$$1 \le i < j \le n$$$, и для всех возможных $$$k$$$ ($$$1 \le k \le n$$$) расстояние от точки $$$p_k$$$ до отрезка, образованного точками $$$p_i$$$ и $$$p_j$$$, не больше $$$R$$$.
Первая строка содержит два целых числа $$$n$$$, $$$R$$$ ($$$1 \le n \le 3000$$$, $$$1 \le R \le 10^5$$$) — количество точек на плоскости и максимальное возможное расстояние от точки до отрезка.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$, $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$), которые задают $$$i$$$-ю точку $$$p_i=(x_i, y_i)$$$. Все точки различны.
Гарантируется, что ответ на задачу не изменится при изменении значения параметра $$$R$$$ на величину не более $$$10^{-2}$$$.
Выведите единственное целое число — количество подходящих пар $$$(i, j)$$$.
4 2 0 1 0 -1 3 0 -3 0
1
3 3 1 -1 -1 -1 0 1
3
В первом примере подходит единственная пара точек $$$(-3, 0)$$$, $$$(3, 0)$$$. Расстояние до отрезка между этими точками от точек $$$(0, 1)$$$ и $$$(0, -1)$$$ равно $$$1$$$, что меньше $$$R=2$$$.
Во втором примере подходят все возможные пары точек.
Название |
---|