Kvadratai

Užduotis

Koordinačių plokštumoje pažymėta N skirtingų taškų. Atkarpomis jungdami kuriuos nors keturis iš tų taškų, galime gauti įvairias geometrines figūras.

Mus domina tokios keturių taškų aibės, kurios būtų kvadrato viršūnėmis.

Užduotis. Iš pažymėtų N taškų išrinkite tokius 4 taškus, kuriuos sujungę gautume didžiausio ploto kvadratą. Jeigu yra keletas sprendinių, pateikite vieną.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas taškų skaičius N (4 <= N <= 1000).

Tolesnėse N eilučių įrašyta po du skaičius – taškų koordinates. Pirmasis skaičius kiekvienoje eilutėje yra atitinkamo taško koordinatė x, o antrasis – koordinatė y.

Koordinatės yra teigiami sveikieji skaičiai, neviršijantys 100 000 000.

Rezultatai

Pirmoje rezultatų eilutėje įrašykite didžiausio rasto kvadrato plotą. Jei nepavyko sudaryti nė vieno kvadrato, pirmoje eilutėje įrašykite nulį.

Jeigu rastas didžiausio ploto kvadratas, antroje eilutėje įrašykite bet kuriai vienai to kvadrato įstrižainei priklausančių viršūnių koordinates: pirmieji du skaičiai reiškia vienos viršūnės koordinates x0 ir y0, antrieji du – antros viršūnės koordinates x1 ir y1 (viršūnių tvarka nesvarbi).

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Iliustracija
5 1 1 3 1 1 3 2 2 3 3	4 1 1 3 3
9 4 4 7 4 4 7 6 7 14 7 4 9 4 11 7 13 11 14	58 14 7 4 11

Pastaba

Didžiausio kvadrato plotas neviršys 10¹⁶. Jam skaičiuoti vartokite int64 (o programuojantys C/C++ – long long) tipą. Naudojant šį duomenų tipą patartina kiekvieną į reiškinį įeinantį kitokio tipo narį versti į int64 tipą.

Pavyzdžiui, jeigu a yra int64 tipo kintamasis, tai priskyrimas:

a := 1000000*1000000;

nebus atliktas korektiškai. Priskyrimą reikia perrašyti taip:

a := int64(1000000)*int64(1000000);

o C ir C++ kalbose:

a = (long long) 1000000 * 1000000;

Tokie pakeitimai yra reikalingi, kadangi priešingu atveju kompiliatorius atliktų operacijas su integer (int) tipo kintamaisiais, gautų integer tipo rezultatą, ir tik tuomet jį paverstų į int64 (long long) tipą.

Pascal kalboje int64 tipo kintamieji išvedami writeln(a), C kalboje – printf("%lld", a), o C++ – cout << a.