Zəncirlə Məhdudlaşdırılmış Yol#3770
Təyyarədə bir neçə dairədən ibarət bir zəncir var. Zəncirlərin ilk (və son) dairəsi yalnız növbəti (və əvvəlki) dairə ilə kəsişir, hər bir aralıq dairə isə yalnız qonşu iki dairə ilə kəsişir.
Sizin vəzifəniz aşağıdakı şərtləri ödəyən ən qısa yolu tapmaqdır:
Yol birinci dairənin və sonuncu dairənin mərkəzlərini birləşdirir.
Yol zəncir daxilindədir, yəni yoldakı bütün nöqtələr ən azı bir dairənin daxilində və ya üzərində yerləşir.
Şəkil 1 belə bir zəncirin və müvafiq ən qısa yolun nümunəsini göstərir.
Şəkil 1: Nümunə zəncir və müvafiq ən qısa yol
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset zəncirin dairələrini aşağıdakı formatda təsvir edir:
Birinci sətrdə (3 \leq n \leq 100) — dairələrin sayı verilir. Növbəti sətrin hər birində x_i, y_i və r_i tam ədədləri verilir. (Bu ədədlər müvafiq olaraq -ci C_i dairəsinin mərkəz koordinatları və radiusudur.) 0 \leq x_i \leq 1000, 0 \leq y_i \leq 1000, 1 \leq r_i \leq 25 olduğu qəbul edilir.
Qəbul edilir ki, C_i və C_{i+1} (1 \leq i \leq n-1) iki fərqli nöqtədə kəsişir. j \geq i+2 üçün C_i və C_j ayrıdır və heç biri digərini əhatə etmir. Həmçinin, heç bir dairə başqa dairənin mərkəzini əhatə etmir.
Girişin sonu bir sıfır olan sətrlə göstərilir.
Şəkil 1 aşağıdakı nümunə girişin birinci datasetsinə uyğundur. Şəkil 2 növbəti datasetlər üçün ən qısa yolları göstərir.
Şəkil 2: Daha çox nümunə zəncirlər və ən qısa yollar
Hər bir dataset üçün, birinci və sonuncu dairənin mərkəzləri arasında zəncir daxilində olan ən qısa yolun uzunluğunu bir sətirdə çıxarın. Cavab -dən böyük olmayan xəta ilə verilməlidir. Çıxışda əlavə simvollar olmamalıdır.
Nümunə 1