Відстеження RFID#4016

Відстеження RFID

1 секунда

64 мегабайти

Середня

Алекс керує складським приміщенням для зберігання товарів компанії North Western Electrical Resource Company (NWERC). Коли клієнт робить замовлення в NWERC, це замовлення передається на склад. Завдання Алекса полягає в тому, щоб знайти замовлені продукти, упакувати їх у коробку та відправити клієнту.

На складі NWERC діє незвичайна політика: товари не мають певного порядку і розкидані по всьому приміщенню. Однак Алекс справляється з завданням, оскільки кожен товар відстежується за допомогою технології RFID. Кожному товару присвоюється бездротовий RFID-чіп, як тільки він потрапляє на склад, а датчики, розташовані на стелі складу, використовуються для автоматичного відстеження продуктів.

За замовчуванням кожен датчик має радіус дії $r$ одиниць — тобто він може зчитувати будь-який RFID-чіп, розташований на відстані не більше $r$ одиниць від нього по прямій лінії. Однак, якщо відрізок між датчиком і продуктом перетинає або торкається $x$ стін, радіус дії датчика зменшується на $x$ одиниць у цьому напрямку. Крім того, датчики можуть не зчитувати RFID-чіп через перешкоди від інших датчиків, тому відстань між будь-якою парою датчиків на складі гарантовано становить щонайменше $r$ одиниць. Ви також можете припустити, що жоден датчик або продукт не розміщений на стіні.

Алекс тепер хоче визначити, для кожного продукту, які датчики можуть зчитувати його RFID-чіп. Чи можете ви йому допомогти?

Ілюстрація датчиків, стін і продуктів, як у прикладі вхідних даних.

Вхідні дані

На першому рядку одне додатне число: кількість тестових випадків, не більше $100$ . Після цього для кожного тестового випадку:

один рядок з чотирма цілими числами $s$ ( $1 \leq s \leq 250000$ 1 \leq s \leq 250000), $r$ ( $1 \leq r \leq 20$ 1 \leq r \leq 20), $w$ ( $0 \leq w \leq 10$ 0 \leq w \leq 10) і $p$ ( $1 \leq p \leq 10000$ 1 \leq p \leq 10000), де $s$ представляє кількість датчиків, $r$ радіус дії кожного датчика, $w$ кількість стін і $p$ кількість продуктів.
$s$ рядків, що містять два цілі числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 10000 \leq x_{i}, y_{i} \leq 10000$ -10000 \leq x_i, y_i \leq 10000). Кожен такий рядок представляє датчик у місці $(x_{i}, y_{i})$ (x_i, y_i). Відстань між будь-якою парою датчиків гарантовано становить щонайменше $r$ одиниць.
$w$ рядків, що містять чотири цілі числа $b x_{i}$ bx_i, $b y_{i}$ by_i, $e x_{i}$ ex_i і $e y_{i}$ ey_i ( $- 10000 \leq b x_{i}, b y_{i}, e x_{i}, e y_{i} \leq 10000$ -10000 \leq bx_i, by_i, ex_i, ey_i \leq 10000). Кожен такий рядок представляє стіну, яку слід розглядати як відрізок прямої від $(b x_{i}, b y_{i})$ (bx_i, by_i) до $(e x_{i}, e y_{i})$ (ex_i, ey_i). Довжина цього відрізка буде додатною.
$p$ рядків, кожен з яких містить два цілі числа $p x_{i}$ px_i і $p y_{i}$ py_i ( $- 10000 \leq p x_{i}, p y_{i} \leq 10000$ -10000 \leq px_i, py_i \leq 10000). Кожен такий рядок представляє продукт у місці $(p x_{i}, p y_{i})$ (px_i, py_i).

Вихідні дані

Для кожного тестового випадку:

$p$ рядків, кожен з яких представляє продукт у порядку, в якому вони з'являються у вхідних даних. Кожен рядок повинен містити ціле число $t$ , кількість датчиків, які можуть відстежувати продукт; це число повинно бути потім доповнене списком з $t$ упорядкованих пар, що представляють відповідні місця розташування датчиків. Якщо є кілька датчиків, вони повинні бути відсортовані у зростаючому порядку за $x$ -координатою. Якщо кілька датчиків мають однакову $x$ -координату, вони повинні бути відсортовані у зростаючому порядку за $y$ -координатою.

Приклади

Приклад 1