Təmir
Beynəlxalq Şəhərdə boru şəbəkəsinin müəyyən bir nöqtəsində su borusunun təmiri planlaşdırılır. Şəbəkə su borusu seqmentlərindən, dayandırıcı klapanlardan və mənbə nöqtəsindən ibarətdir. Su borusu 2D mühitində bir seqmentlə təmsil olunur və kəsişən su borusu seqmentləri kəsişmə nöqtəsində birləşir. Təmirlə məşğul olarkən, suyun təmir nöqtəsinə axmasının qarşısını alan dayandırıcı klapanlar bəzi su borusu seqmentlərində bir nöqtə ilə təmsil olunur. Şəbəkədə yalnız bir mənbə nöqtəsi mövcuddur və su bu nöqtədən şəbəkəyə təmin edilir.
Təmir zamanı bəzi ərazilərdə su təchizatını dayandırmalıyıq, lakin iğtişaş riskini azaltmaq üçün su təchizatını dayandıran su borularının uzunluğunu minimuma endirmək lazımdır. Sizin vəzifəniz, su borusu seqmentlərinin son nöqtələrinin koordinatları, dayandırıcı klapanlar, mənbə nöqtəsi və təmir nöqtəsi verildikdə, su təchizatını dayandırmaq üçün lazım olan su borularının uzunluğunu minimuma endirmək üçün bir proqram yazmaqdır.
Giriş verilənləri
Məlumat dəsti aşağıdakı formatdadır:
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
Girişin ilk sətri iki tam ədəd, N (1 ≤ N ≤ 300) və M (0 ≤ M ≤ 1000) ehtiva edir ki, bunlar su borusu seqmentlərinin və dayandırıcı klapanların sayını göstərir. Sonrakı N sətir su borusu seqmentlərinin son nöqtələrinin koordinatlarını təsvir edir. i-ci sətir i-ci su borusu seqmentinin son nöqtələrinin koordinatlarını göstərən dörd tam ədəd, x_si, y_si, x_di və y_di ehtiva edir. Sonrakı M sətir dayandırıcı klapanların nöqtələrini təsvir edir. i-ci sətir i-ci dayandırıcı klapanın koordinatını göstərən iki tam ədəd, x_vi və y_vi ehtiva edir. Sonrakı sətir mənbə nöqtəsinin koordinatını göstərən iki tam ədəd, x_b və y_b ehtiva edir. Sonuncu sətir təmir nöqtəsinin koordinatını göstərən iki tam ədəd, x_c və y_c ehtiva edir.
Hər hansı koordinat tam ədədlərinin mütləq dəyərlərinin 1000-dən (daxil olmaqla) kiçik olduğunu qəbul edə bilərsiniz. Həmçinin, dayandırıcı klapanların, mənbə nöqtəsinin və təmir nöqtəsinin həmişə bir su borusu seqmentində olduğunu və dayandırıcı klapanlar, mənbə nöqtəsi və təmir nöqtəsi arasında hər bir cütün fərqli olduğunu qəbul edə bilərsiniz. Hər bir su borusu seqmenti cütü arasında bir dəfədən çox kəsişmə yoxdur. Nəhayət, su borusu şəbəkəsi bağlıdır, yəni bütün su boruları əvvəlcə su təchizatı alır.
Çıxış verilənləri
Bir sətirdə su təchizatını dayandırmaq üçün lazım olan minimal su borularının uzunluğunu çap edin. Mütləq və ya nisbi səhv 10^{−6}-dan az olmalıdır. Bütün dayandırıcı klapanları bağlasanız belə, təmir nöqtəsinə su təchizatını dayandıra bilmirsinizsə, bir sətirdə "-1" çap edin.