Noise
Есенен Турнир по Информатика 2007
Time Limit: 0.2s, Memory Limit: 36MiB
Класът на Елеонора е адски Шумен. Дори Големият Взрив е като слабо припукване в сравнение с него! Ели е забелязала, че главната причина за това е фактът, че всеки се опитва да говори с хора, които в повечето случаи са в другата част на стаята. А както е широко известно – когато два събеседника си говорят, силата на звука нараства квадратично спрямо разстоянието между тях.

Един ден Ели се запитала каква е максималната олелия, която може да се постигне в нейния клас. На нея ѝ е достатъчно да знае само какви са разстоянията на квадрат между всеки двама събеседника, за да определи какъв шум се вдига. По-точно, в случая нея я интересува сборът на всички такива разстояния. Тъй като тя е в нормално българско училище, веднага ви става ясно, че абсолютно всички ученици си говорят по време на часовете. Нейният клас се състои от N човека, като N е четно. Всеки ученик води точно по един разговор с някой от останалите N-1, като двамата си говорят помежду си и с никой друг.

Ели е дете на прецизността, за това тя мери разстоянията в сантиметри. Нейната класна стая е 10 на 10 метра, тоест 1000 на 1000 сантиметра. Тя може да определи къде стои някой нейн съученик спрямо единия ъгъл на стаята, който за по-удобно тя определя като (0, 0).

По дадено разположение на N-те човека в класната стая, определете какъв е най-големият шум, който може да се постигне (сборът на квадратите на разстоянията между говорещите си ученици).
Вход
На първия ред на стандартния вход е зададено едно цяло число N - броят ученици в класа. На следващите N реда ще намерите по две цели числа Xi Yi - координатите на всеки ученик. Възможно е да има ученици с еднакви координати - например момиче, седнало в гаджето си.
Изход
На единствен ред на стандартния изход изведете едно цяло число – максималния сбор от квадрати на разстоянията, ако точките се свържат оптимално.
Ограничения
  • 1 ≤ N ≤ 24
  • 0 ≤ Xi, Yi ≤ 1,000
  • Гарантирано е, че N ще е четно.
Примерен Вход Примерен Изход
6 0 0 5 7 3 2 6 6 5 1 4 2 109
Оптималният отговор се получава при свързване на (0, 0) с (6, 6) за разстояние 72; (5, 1) с (5, 7) за разстояние 36; и (3, 2) с (4, 2) за разстояние 1.
Мрън!