Радиация
Атомные электростанции (АЭС) представляют собой одновременно и благо, и угрозу для современной цивилизации. Несмотря на определенные риски, АЭС остаются одним из наиболее экономичных способов производства электроэнергии в развитых странах. В этой задаче мы рассмотрим ситуацию с двумя атомными станциями, расположенными близко друг к другу.
Рисунок 1: Две атомные электростанции. Дома в точках (81, 49) и (77,33) находятся в зоне высокого риска от обеих станций.
Мы будем описывать ситуацию на плоской местности, используя двумерную декартову систему координат для обозначения каждого местоположения. Пусть координаты двух атомных электростанций — (a_x, a_y) и (b_x, b_y). Дома, находящиеся на расстоянии R_1 (включительно) от станции в точке (a_x, a_y), считаются в зоне высокого риска радиации. Аналогично, дома, находящиеся на расстоянии R_2 (включительно) от станции в точке (b_x, b_y), также находятся в зоне высокого риска. Поэтому власти станций 1 и 2 предоставляют специальные защитные средства для домов, находящихся в радиусе R_1 и R_2 от соответствующих станций. В результате каждый дом, находящийся под угрозой от обеих станций, получает два комплекта оборудования для защиты, хотя одного комплекта достаточно для полной защиты. Дома, находящиеся за пределами зоны высокого риска, считаются в зоне низкого риска радиации и не получают защитного оборудования из-за бюджетных ограничений. Однако владельцы домов, имеющих два комплекта защитного оборудования, передают один комплект владельцам домов, у которых его нет. Тем не менее, некоторые дома в зоне низкого риска остаются незащищенными. Учитывая местоположение домов и значения a_x, a_y, b_x, b_y, а также возможные значения R_1 и R_2, ваша задача — определить количество домов, которые остаются без защитного оборудования для каждой пары значений R_1 и R_2.
Входные данные
Входной файл содержит не более 3 тестовых случаев. Описание каждого тестового случая приведено ниже:
Тестовый случай начинается с строки, содержащей положительное целое число N (0 < N ≤ 200000), обозначающее количество домов, находящихся либо в зоне низкого, либо в зоне высокого риска радиации. Каждая из следующих N строк содержит два целых числа x_i, y_i (0 ≤ x_i, y_i ≤ 20000), которые обозначают координаты i-го дома. Ни два дома не находятся в одном и том же месте. Следующая строка содержит пять целых чисел a_x, a_y, b_x, b_y и q (0 ≤ a_x, a_y, b_x, b_y ≤ 20000, 0 < q ≤ 20000). Значения a_x, a_y, b_x и b_y даны в условии задачи. Здесь q обозначает общее количество запросов. Каждая из следующих q строк содержит два целых числа, обозначающих значения R_1 и R_2 (0 < R_1, R_2 ≤ 13000) соответственно.
Строка, содержащая один ноль, завершает ввод. Эта строка не должна обрабатываться.
Выходные данные
Для каждого тестового случая создайте q+1 строк вывода. Первая строка — это номер вывода. Для каждого запроса (данное значение R_1 и R_2) определите, сколько домов в зоне низкого риска остаются без защитного оборудования. Вы можете рассмотреть возможность использования более быстрого ввода-вывода, так как файл ввода судьи большой.
Примечание: Первый запрос в примере ввода соответствует Рисунку 1.