геометрия

Дан угол AOB (O - вершина угла, A и B - точки на сторонах) и точка P. Определите, принадлежит ли точка P углу AOB (включая его стороны: лучи OA и OB).

 

Входные данные

Программа получает на вход координаты точек A, O, B, P.  Все координаты - целые, не превосходят 100 по модулю. Точки A, O, B не лежат на одной прямой.

 

Выходные данные

Программа должна вывести слово YES или NO.

Ввод	Вывод
0 1 0 0 1 0 1 1	YES

Антон  сторож на очень важном объекте. Как и положено всем важным объектам, он обнесён забором. Правда, время не пощадило этот забор, и в нём есть дыры, через которые на объект могут попадать нарушители.

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

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

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

Формат входных данных
В первой строке входного файла содержится три целых числа n (3 <= n <= 10⁵)  количество столбов в заборе, l (0 <= l  <= 10¹⁸)  длина выданного Антону мотка проволоки и k (0 <= k   <=n/2) количество дыр в заборе.

Во второй строке по возрастанию заданы k чисел a_i (1 < a_i <= n). Числу ai соответствует отсутствие секции забора между столбами a_i и a_i+1 mod n. Гарантируется, что из двух соседних секций хотя бы одна не отсутствует.

В следующих n строках находится по два целых числа x_i и y_i (|xi| <= 10¹⁸, |y_i| <= 10¹⁸)  координаты i-го столба забора. Многоугольник может быть задан в порядке обхода как по, так и против часовой стрелки.

Формат выходных данных

Выведите единственное число  минимальную суммарную длину дыр в заборе после установки колючей проволоки. Ответ будет считаться правильным, если если он отличается от правильного не более, чем на p · 10^?6

, где p  периметр многоугольника.

Примеры

Ввод	Вывод
6 4 3 1 3 5 0 0 3 0 4 1 3 2 0 2 -1 1	2.82842712474619

Петя и Вася — хорошие друзья. Поэтому они часто ездят друг к другу в гости. Недавно Петя

получил водительские права и собирается навестить своего друга. Для простоты будем считать, что

все дороги в городе, в котором они живут, являются бесконечными прямыми. В месте пересечения

двух или более дорог находятся перекрестки. Дома Пети и Васи расположены возле некоторых

дорог города, но не на перекрестках.

Петя начинает путь на дороге возле своего дома. При этом он может выбрать любое из

двух направлений. Когда Петя подъезжает к перекрестку, он может повернуть на любую другую

проходящую через него дорогу или продолжить ехать по текущей. Поскольку Петя не очень

опытный водитель, каждый поворот, который он совершает, заставляет его волноваться. Причем

волнение Пети равно величине угла, на который он поворачивает, в градусах. Например, при

повороте на прямой угол волнение Пети равно 90.

При менее крутом повороте Петя волнуется меньше, а при более крутом — сильнее.

 Будем считать, что волнение Пети в течении всего маршрута равно сумме величин в

3

0 0 2 0

1 1 0 2

1 2 3 2

-3 0

3 2
Вывод
270.0

Ввод