Ремонт
У Міжнародному Місті Будівництва Труб планується ремонт водопроводу в певній точці мережі. Мережа складається з сегментів труб, запірних клапанів та джерела. Водопровід представлений сегментами на 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" в одному рядку.