Zəncir
İzotetik düzbucaqlı nəzərdən keçirək, burada "izotetik" koordinat oxlarına paralel tərəfləri olan deməkdir. Bu düzbucaqlının sol alt küncünün koordinatları (0, 0), sağ üst küncünün koordinatları isə (x_max, y_max) təşkil edir. Düzbucaqlının daxilində N nöqtə yerləşir: P_1 (x_1, y_1), P_2 (x_2, y_2), …, P_N (x_N, y_N) və bu nöqtələr 0 < x_i < x_max, 0 < y_i < y_max şərtlərini ödəyir. Aşağıdakı şərtləri təmin edən çoxbucaqlı zəncirlər SP_i1P_i2...P_ikF nəzərdən keçirək:
Bütün daxili təpələr P_ij verilmiş nöqtələrdən seçilir; seçilmiş nöqtələrin sayı 0 ≤ k ≤ N ola bilər;
Başlanğıc təpə S (x_S, y_S) düzbucaqlının sol tərəfində və ya onun solunda yerləşir (x_S ≤ 0, 0 ≤ y_S ≤ y_max);
Son təpə F (x_F, y_F) düzbucaqlının sağ tərəfində və ya onun sağında yerləşir (x_F ≥ x_max, 0 ≤ y_F ≤ y_max).
Belə bir zənciri sabit uzunluqlu adlandıraq ki, yalnız bütün seqmentlərin Evklid uzunluqları bərabər olsun (|SP_i1| = |P_i1P_i2| = ... = |P_ikF|). Asanlıqla görmək olar ki, istənilən düzbucaqlı və verilmiş nöqtələr dəsti üçün ən azı bir sabit uzunluqlu çoxbucaqlı zəncir mövcuddur: bu, bütün şərtləri təmin edən S(0, 0) və F(x_max, 0) koordinatları ilə SF seqmentidir.
Sizin vəzifəniz, seqmentin minimal uzunluğuna malik sabit uzunluqlu zənciri tapmaq üçün proqram yazmaqdır. Asanlıqla görmək olar ki, minimal uzunluğun kvadratı (ikinci dərəcə) həmişə tam ədəddir, buna görə proqram uzunluğun kvadratını tam ədəd kimi çıxarmalıdır.
Giriş verilənləri
Girişin ilk sətri üç boşluqla ayrılmış tam ədəd x_max, y_max, N ehtiva edir — sağ üst küncün koordinatları və verilmiş nöqtələrin sayı. Növbəti N sətirin hər biri iki boşluqla ayrılmış tam ədəd x_i, y_i ehtiva edir — verilmiş nöqtənin koordinatları.
Məhdudiyyətlər: 1 ≤ N ≤ 1000; 5 ≤ x_max, y_max ≤ 32000; bütün 1 ≤ i ≤ N üçün, 0 < x_i < x_max, 0 < y_i < y_max.
Çıxış verilənləri
Proqramınız dəqiq bir tam ədəd yazmalıdır: sabit uzunluqlu çoxbucaqlı zəncirlər arasında mümkün olan minimal seqment uzunluğunun kvadratı.
Qeyd: Bəzi sabit uzunluqlu zəncirlər qurmaq mümkündür (məsələn: (–2, 6), (2, 8), (6, 6), (6+, 6)), lakin daha kiçik uzunluqlar üçün heç bir sabit uzunluqlu zəncir qurmaq mümkün deyil.