НачалоПодразделы
| 790. Word Ladder |
| 791. Bonus Word |
| 792. Contest |
| 793. Cycling |
| 794. Escape |
| 795. Settling Salesman Problem |
| 796. Space |
| 797. Herbert |
Другие разделы
| Тренировка 1 |
| Тренировка 2 |
| Тренировка 3 |
| Тренировка 4 |
Дата и время
17/11/2024 01:19:03
Тренировка 5
A. Word Ladder B. Bonus Word C. Contest D. Cycling E. Escape F. Settling Salesman Problem G. Space H. Herbert
G. Space
Бинарный поискСортировка
Олимпиадные задачи на английском языке
| 08/02/2008 | Тренировка (задачи Benelux APC preliminary 2007) (G) |
| 11/07/2013 | Лето 2013-8 (G) |
Ограничения: время – 15s/20s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
During a programming contest, teams can’t sit close to each other, because then a team
might copy the solution of another team. You are given the locations of the teams and the
minimum required Euclidian distance between two teams. You have to find the number of
pairs of teams that sit too close to each other.
Input
On the first line an integer `t` (`1\ ≤\ t\ ≤\ 100`): the number of test cases. Then for each test
case:
- One line with two integers `n` (`1\ ≤\ n\ ≤\ 100\ 000`) and `d` (`1\ ≤\ d\ ≤\ 50`): the number of teams and the minimum distance between two teams.
- `n` lines with two integers `x_i` (`0\ ≤\ x_i\ ≤\ 1\ 000\ 000\ 000`) and `y_i` (`0\ ≤\ y_i\ ≤\ 1\ 000\ 000\ 000`): the coordinates of the `i`-th team. No two teams will have the same coordinates.
Output
For each test case:
- One line with the number of pairs of teams that sit too close to each other.
Notes
The Euclidean distance between points `(x_1,\ y_1)` and `(x_2,\ y_2)` is `sqrt((x_1\ -\ x_2)^2\ +\ (y_1\ -\ y_2)^2)`.
Sample input
1 6 3 0 0 0 3 2 1 2 3 3 0 3 1
Sample output
8
