Ziqzaq#5795
Verilmiş bir neçə nöqtəni müstəvidə birləşdirərək zigzag xətti tapmağa çalışaq. Məqsəd, verilmiş bütün nöqtələrdən keçən və minimal dönmə nöqtələrinə malik zigzag xəttini tapmaqdır. Əgər minimal dönmə nöqtələrinə malik bir neçə zigzag xətti varsa, onların arasında ən qısa olanı seçilməlidir.
Məsələn, Şəkil 1-də verilmiş doqquz nöqtəni nəzərdən keçirək.
Şəkil 1: Verilmiş doqquz nöqtə
Zigzag xətti bir neçə düz xətt seqmentindən ibarətdir. Burada qayda tələb edir ki, hər bir xətt seqmenti iki və ya daha çox verilmiş nöqtədən keçməlidir.
Zigzag xətti bəzi verilmiş nöqtələrdə və ya başqa yerlərdə dönə bilər. Bəzi verilmiş nöqtələrdən bir neçə dəfə keçilə bilər.
Şəkil 2: Üç dönmə nöqtəsi olan zigzag xətləri.
Üç dönmə nöqtəsi olan iki zigzag xətti Şəkil 2 (a) və (b)-də Şəkil 1-də göstərilən eyni verilmiş nöqtələr dəsti üçün təsvir edilmişdir. Şəkil 2 (a)-dakı zigzag xəttinin uzunluğu Şəkil 2 (b)-dəki xəttdən qısadır. Əslində, Şəkil 2 (a)-dakı zigzag xəttinin uzunluğu ən qısa olduğundan, bu, Şəkil 1-də verilmiş doqquz nöqtə üçün həll yoludur.
Dörd dönmə nöqtəsi olan başqa bir zigzag xətti Şəkil 3-də təsvir edilmişdir. Onun uzunluğu Şəkil 2-dəki xətlərdən qısadır, lakin dönmə nöqtələrinin sayı Şəkil 2-dəki xətlərdən çoxdur və buna görə də həll yolu deyil.
uzunluq= 10.0
Şəkil 3: Dörd dönmə nöqtəsi olan zigzag xətti.
Şəkil 4 (a) və (b)-də təsvir edilmiş verilmiş nöqtələr dəsti üzərindən keçən iki zigzag xətti var.
Hər ikisinin dönmə nöqtələrinin sayı eynidir və (a)-dakı xətt (b)-dəki xətdən uzundur. Lakin həll (a)-dır, çünki (b)-dəki zigzag xəttinin seqmentlərindən biri yalnız bir verilmiş nöqtədən keçir, bu da qaydanı pozur.
Şəkil 4: İki dönmə nöqtəsi olan zigzag xətti (a) və qaydaya uyğun olmayan zigzag xətti (b).
Sizin işiniz bu tapmacanı həll edən bir proqram yazmaqdır.
Giriş bir neçə datasetdən ibarətdir, ardınca bir sıfır olan bir sətir gəlir. Hər bir dataset aşağıdakı formatdadır.
n
x_1 y_1
...
x_n y_n
Hər bir datasetdəki giriş elementi qeyri-mənfi tam ədəddir. Sətirdəki elementlər bir boşluqla ayrılır.
n verilmiş nöqtələrin sayıdır. x_k və y_k (k = 1, ..., n) k-cı nöqtənin mövqeyini göstərir. Nöqtələrin sırası əhəmiyyətsizdir. Sizə verilmişdir ki, 2 ≤ n ≤ 10, 0 ≤ x_k ≤ 10 və 0 ≤ y_k ≤ 10.
Hər bir dataset üçün minimal dönmə nöqtələrinin sayı və həmin dönmə nöqtələrinin sayına malik ən qısa zigzag xəttinin uzunluğu bir sətirdə boşluqla ayrılmış şəkildə çap edilməlidir. Uzunluq onluq kəsr şəklində 0.0001 (= 1.0 × 10^{−4}) səhvdən az olmalıdır.
Siz əmin ola bilərsiniz ki, minimal dönmə nöqtələrinin sayı ən çox dörddür, yəni xətt seqmentlərinin sayı ən çox beşdir.
Nümunə girişlərdəki ilk dörd dataset üçün həllər Şəkil 5 və 6-da təsvir edilmişdir.
Şəkil 5: Nümunə girişlərdəki birinci və ikinci datasetlər üçün həllər.
Şəkil 6: Nümunə girişlərdəki üçüncü və dördüncü datasetlər üçün həllər.
Nümunə 1