Ремонт
В Международном Городе Строительства Труб планируется ремонт водопровода в определенной точке сети трубопроводов. Сеть состоит из сегментов труб, запорных клапанов и источника. Каждый сегмент трубы представлен на 2D-плоскости, и пересекающиеся сегменты соединены в точке пересечения. Запорный клапан, который предотвращает поступление воды в ремонтируемую точку во время ремонта, представлен точкой на каком-либо сегменте трубы. В сети имеется только одна точка источника, из которой вода поступает в сеть.
Во время ремонта необходимо прекратить подачу воды в некоторых районах, но чтобы минимизировать неудобства, длина труб, в которых прекращается подача воды, должна быть минимальной. Ваша задача — написать программу, которая минимизирует длину труб, необходимых для прекращения подачи воды, при заданных координатах конечных точек сегментов труб, запорных клапанов, точки источника и точки ремонта.
Входные данные
Формат входных данных следующий:
N M
x_s1 y_s1 x_d1 y_d1
...
x_sN y_sN x_dN y_dN
x_v1 y_v1
...
x_vM y_vM
x_b y_b
x_c y_c
Первая строка входных данных содержит два целых числа, N (1 ≤ N ≤ 300) и M (0 ≤ M ≤ 1000), которые обозначают количество сегментов труб и запорных клапанов. Следующие N строк описывают конечные точки сегментов труб. i-я строка содержит четыре целых числа, x_si, y_si, x_di и y_di, которые обозначают координаты конечных точек i-го сегмента трубы. Следующие M строк описывают точки запорных клапанов. i-я строка содержит два целых числа, x_vi и y_vi, которые обозначают координаты i-го запорного клапана. Следующая строка содержит два целых числа, x_b и y_b, которые обозначают координаты точки источника. Последняя строка содержит два целых числа, x_c и y_c, которые обозначают координаты точки ремонта.
Вы можете предположить, что любые абсолютные значения целых чисел координат меньше 1000 (включительно). Также можно предположить, что каждый запорный клапан, точка источника и точка ремонта всегда находятся на одном из сегментов труб, и каждая из этих точек уникальна. Между каждой парой сегментов труб не более одного пересечения. Наконец, сеть труб соединена, то есть все трубы изначально получают водоснабжение.
Выходные данные
Выведите минимальную длину труб, необходимых для прекращения подачи воды, в одной строке. Абсолютная или относительная ошибка должна быть меньше или равна 10^{−6}. Если невозможно прекратить подачу воды в точку ремонта, даже если закрыть все запорные клапаны, выведите "-1" в одной строке.