Geometrik Xəritə#5830
Bu məsələdə tapşırığınız, bir düz müstəvidə xətt parçalarından ibarət verilmiş bir küçə xəritəsində verilmiş iki nöqtə arasında ən qısa yolu tapan bir proqram yazmaqdır.
Şəkil 1: Küçə xəritəsinə nümunə
Şəkil 1-də bəzi xətt parçaları küçələri, digərləri isə avtomobillərin hərəkət edə bilmədiyi istiqamətləri göstərən işarələri təmsil edir. Xüsusilə, AE, AM, MQ, EQ, CP və HJ küçələri təmsil edir; digər xətlər işarələrdir. Ümumiyyətlə, bir işarənin bir ucu dəqiq bir küçə seqmentinə toxunur, digər ucu isə açıqdır. Hər küçənin hər bir ucu bir və ya daha artıq küçəyə toxuna bilər, amma heç bir işarəyə toxunmur.
Məsələn, BF işarəsi göstərir ki, B nöqtəsində avtomobillər yalnız soldan sağa hərəkət edə bilər, əks istiqamətdə isə hərəkət edə bilməz. Ümumiyyətlə, avtomobillər bir işarənin küçəyə toxunduğu nöqtədə küt bucaq tərəfdən iti bucaq tərəfə hərəkət edə bilməz (məsələn, CBF bucağı küt, ABF bucağı isə itidir). Avtomobillər nə P-dən M-ə, nə də M-dən P-yə birbaşa hərəkət edə bilməzlər, çünki soldan sağa hərəkət edənlər N-dən keçə bilməz və sağdan sola hərəkət edənlər O-dan keçə bilməz. Əgər işarə ilə küçə arasındakı bucaq düzbucaqlıdırsa, həmin nöqtədə heç bir istiqamətdə hərəkət mümkün deyil. Məsələn, H-dən J-yə və ya J-dən H-yə birbaşa hərəkət mümkün deyil.
Bu yol hərəkəti qaydalarına riayət edən ən qısa yolu tapan proqram yazmalısınız. (x_1, y_1) və (x_2, y_2) arasındakı bir parça uzunluğu adi Evklid məsafəsidir.
Giriş bir neçə datasetdən ibarətdir, hər biri aşağıdakı formatda verilmişdir:
x_s~y_s
x_g~y_g
x^1_1~y^1_1~x^1_2~y^1_2
...
x^k_1~y^k_1~x^k_2~y^k_2
...
x^n_1~y^n_1~x^n_2~y^n_2
— xətt parçalarının sayı, -dən çox olmayan müsbət tam ədəddir.
(x_s, y_s) və (x_g, y_g) başlanğıc və son nöqtələrdir. (x_s, y_s) \neq (x_g, y_g) və hər biri bəzi küçə seqmentinin ucu üzərində yerləşir. Bundan əlavə, (x_s, y_s)-dən (x_g, y_g)-yə ən qısa yolun unikal olduğu qəbul olunur.
(x^k_1, y^k_1) və (x^k_2, y^k_2) -cı seqmentin iki ucudur. (x^k_1, y^k_1) \neq (x^k_2, y^k_2). İki parça yalnız uclarında toxuna bilər, heç vaxt kəsişmir və üst-üstə düşmür.
Bütün koordinatlar -dən artıq olmayan qeyri-mənfi tam ədədlərdir. Girişin sonu tək sətirdə bir sıfır ilə göstərilir.
Hər dataset üçün başlanğıc nöqtədən son nöqtəyə qədər ən qısa yolda olan hər bir küçə kəsişmə nöqtəsini ardıcıllıqla hər sətrdə, ardınca bir sıfır olan sətrdə çap edin. Küçə kəsişmə nöqtəsi — ən azı iki küçə xətt seqmentinin toxunduğu nöqtədir. Hər bir küçə kəsişmə nöqtəsi üçün çıxış sətri və koordinatlarını arada boşluq olmaqla göstərməlidir.
Əgər başlanğıcdan sona heç bir yol yoxdursa, çap edin.
Nümunə 1