Задача D. Принцесса ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Принцесса Евлампия живет в замке, окруженном забором. Жизнь принцессы тяжела, но при этом и очень интересна. Главным ее развлечением является общение с многочисленными поклонниками, постоянно прибывающими из соседних замков, городов и даже королевств.

Замок принцессы окружен забором, представляющим из себя выпуклый многоугольник. Отец принцессы, король, достаточно строг, поэтому всем поклонникам принцессы приходится попадать туда через единственную во всем заборе дырку, вместо того, чтобы войти на территорию замка через парадные ворота. Дырка находится в одной из вершин многоугольника. При этом, если пройти напрямую к дырке поклоннику не удается, ему приходится обходить забор вдоль его периметра. Естественно, каждому поклоннику интересно, сколько ему придется пройти, чтобы попасть из точки своего начального местоположения к дырке, и все спрашивают об этом принцессу, перед тем как прийти к ней в гости.

Принцесса составила список начальных местоположений всех своих поклонников и описание забора вокруг замка. Вам необходимо для каждого поклонника сообщить длину кратчайшего пути от точки его начального положения до точки, в которой находится дырка. При этом, естественно, ни одна точка этого пути не должна лежать внутри многоугольника, представляющего забор, но может лежать на его границе.

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 30 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 100.

Вторая группа тестов проверяется в момент сдачи задачи на проверку и стоит 30 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 10 000.

Третья группа тестов проверяется после окончания олимпиады и стоит 40 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке входного файла находятся два целых числа n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — количество вершин в многоугольнике, представляющем забор, и номер вершины, в которой находится дырка. В следующих n строках содержатся пары целых чисел x_i и y_i, описывающих координаты вершин многоугольника в порядке обхода против часовой стрелки.

В следующей строке дано одно целое число m (1 ≤ m ≤ 100 000) — количество поклонников принцессы. В следующих m строках содержатся пары целых чисел x_i и y_i, описывающих координаты начального положения очередного поклонника.

Все координаты не превышают 10⁹ по абсолютной величине.

Формат выходного файла

Для каждого поклонника выведите одно число — ответ на задачу. Ответ должен отличаться от правильного не более, чем на 10⁻⁵.

Примеры тестов

4 2
0 1
0 0
1 0
1 1
2
2 2
-2 0

3.23606797
2.0