Sərhəd
Liliputiyanın sərhəd zolağı sahəsi sıfır olmayan qapalı çoxbucaqlı formasındadır. Çoxbucaqlının təpə nöqtələri bir-biri ilə düz xətt ilə əlaqələndirilmiş keşikçi qülləsidir. Bu sərhəd Liliputiya üçün çox uzundur və saxlamaq da baha başa gəlir. Buna görə də ölkə hökuməti qısaltmaq üçün sərhəddə yenidən baxmaq qərarına gəldi. Lakin onlar yeni keşikçi qülləsi qurmaq istəmirlər, olanları yeni sərhəd üçün istifadə etmək istəyirlər.
Hər gün gözətçilər sərhəddə nəzarət edirlər. Onlar saat əqrəbi istiqamətində sərhədboyunca qülləri bir-bir dolaşırlar. Keşikçı qülləri onları dolaşma ardıcıllığına uyğun olaraq 1-dən N-ə qədər nömrələnmişdir. Sərhədlərin yenilənməsi şərh edildiyi kimi onları dolaşma metodunu dəyişməməlidir, Liliputuyanın sahəsi isə sıfır qalmamalıdır.
Məsələn, şəkildə göstərilmiş sərhəddi (miqyas kilometrlə verilmişdir) uzunluğu 57.89 kilometr olan 1-2-3-4-5-1 yolu ilə dolaşmaq olar. Sərhəddin uzunluğunu mümkün qədər azaltmaq üçün Liliputiya ona elə yenidən baxmalıdır ki, uzunluğunu 27.31 kilometrə qədər qısaltmaqla onu 2-3-4-2 yolu ilə dolaşmaq mümkün olsun.
Liliputuyada onun qürüru olan bir nüçə tarixi abidə var. Tarixi abidələr istənilən halda Liliputiyanın sərhədləri daxilində qalmalıdır və nəticə olaraq onlar sərhəd üzərində qalmamalıdırlar. Sizə bütün tarixi abidələrin Liliputiya sərhədləri daxilində qalması üçün ən qısa sərhədin planını hazırlamaq lazımdır.
Şəkildə iki tarixi abidə "A" və "B" simvolu ilə işarə edilmişdir. Onları Liliputiya daxilində saxlamaq üçün uzunluğu 51.78 kilometr olan 1-2-3-4-1 yolu ilə sərhəd şəkmək lazımdır.
Giriş verilənləri
İlk sətir boşluqla ayrılmış iki N və M tam ədədlərini ehtiva edir. N (3 ≤ N ≤ 50) - Liliputiya sərhəddindəki qüllələrin sayıdır. M (0 ≤ M ≤ 1000) - Liliputiya daxilindəki tarixi abidələrin sayıdır.
Növbəti N sətir saat əqrəbinin hərəkət istiqamətində keşikçi qəllərinin koordinatlarını ehtiva edir. Növbəti M sətir isə abidələrin koordinatlarını ehtiva edir. Bütün koordinatlar tam ədədlər cütlüyü (uyğun olaraq X və Y) ilə verilir və boşluqla ayrılır. Koordinatlar kilometrlə verilir, hər bir qiymət modulca 10000-ni aşmır. Bütün keşikçi qüllələri müxtəlif yerlərdə yerləşirlər.
Çıxış verilənləri
Yeganə həqiqi ədədi – Liliputiyanın yeni sərhəddinin mümkün minimal uzunluğunu onluq nöqtədən sonra iki işarə dəqiqliyi ilə verin.