Halka yolu üçün sürət diametri
Yeni Flathburq şəhərinin meri İvan Kotyanin, şəhərdəki tıxac problemlərini həll etmək məqsədilə işə başladı. Flathburqda, digər böyük şəhərlər kimi, dairəvi avtomobil yolu mövcuddur. Bu yol, monoton çoxbucaqlı formasındadır. Monoton çoxbucaqlı, şimaldan cənuba doğru keçən hər bir düz xəttin ən çox iki ortaq nöqtəsi olan çoxbucaqlıdır.
Şəhər hökuməti ilə keçirilən iclasdan sonra, dairəvi yolun iki nöqtəsini birləşdirən və şimaldan cənuba doğru uzanan yeni bir magistral yolun tikilməsi qərara alındı.
Tıxacları azaltmaqla yanaşı, şimaldan cənuba çəkilən ən uzun magistralın uzunluq rekordunu yeniləmək də məqsəd qoyuldu. Rekordu yeniləmək üçün magistralın uzunluğu ən azı d kilometr olmalıdır və Flathburq büdcəsində artıq pul olmadığı üçün yolun uzunluğu dəqiq d olaraq qərarlaşdırıldı.
Flathburq nəqliyyat naziri, merə yeni yolun tikintisi üçün bütün mümkün variantları təqdim etmək qərarına gəldi. İlk növbədə, magistralın tikilməsi üçün neçə yol olduğunu hesablamaq lazımdır. Nazira bu məsələdə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətiri, dairəvi avtomobil yolunu təyin edən çoxbucaqlının təpələrinin sayı n (3 ≤ n ≤ 100000) və yeni magistralın uzunluğu d (1 ≤ d ≤ 10^8) olan iki tam ədədi ehtiva edir.
Daha sonra təpələrin yerləşməsi təsvir edilir - növbəti n sətirin hər biri müvafiq təpənin koordinatlarını x və y (-10^8 ≤ x, y ≤ 10^8) ehtiva edir. Təpələr saat əqrəbi istiqamətinin əksinə olaraq verilir.
Şimaldan cənuba doğru olan istiqamət x = c tənliyi ilə müəyyən edilən düz xətlərə uyğundur. Verilən çoxbucaqlı monotondur.
Çıxış verilənləri
Çıxış faylında dəqiq d uzunluğunda əlavə magistral tikmək üçün yolların sayını göstərin. Əgər tikinti yolları sonsuz saydadırsa, çıxış faylında "Infinity" yazın.