Преписивачи
Аутор: Павле Мартиновић
Текст и тест примери: Алекса Милојевић
Анализа решења: Момчило Тошић
Тестирање: Владимир Миленковић
Приметимо прво да је удаљеност тачака са координатама (x_A, y_A) и (x_B, y_B) једнака \sqrt{(x_A-x_B)^2 + (y_B-y_А)^2}, а провера да ли су паралелне праве одређена овим двема, и тачкама (x_C, y_C) (x_D, y_D) је провера једнакости коефицијента правца ових права \frac{y_А-y_B}{x_А-x_B}=\frac{y_C-y_D}{x_C-x_D}, што како бисмо избегли дељење нулом можемо записати овако: (y_A-y_B)(x_C-x_D) = (x_A-x_B)(y_C-y_D).
Случај N \leq 4
Уколико је N мање од 4, јасно је да нема решења. Уколико је N тачно 4, можемо покушати да обележимо унете тачке са A,B,C,D у сваком редоследу и да проверимо да ли важи релација дата у задатку (да су праве AB и CD паралелне и да је удаљеност између A и B два пута мања од удаљености између C и D или обратно).
Случај N \leq 100
Можемо фиксирати било које 4 тачке и проверити да ли важи релација (прву фиксирану означимо са А, другу са B итд).
Случај N \leq 400
Можемо приметити да ако фиксирамо A, B, и C, тачка D се налази на јединственој правој кроз C, и то на јединственој удаљености (два пута мањој од \overline{CD}), те треба посматрати само 2 могућности за тачку D: тачка на тој правој на удаљености \overline{AB}/2 “лево” и “десно” од C. Ако додамо те тачке у почетни низ и сортирамо, свако додатно појављивање неке тачке m пута значи да та тачка може бити на краћој основици за m тројки, те је решење збир свих m вредности за све тачке, подељено са 2 (јер смо урачунали обе тачке краће основице).
Сви поени
Ако посматрамо пример сумњивог четвороугла, може нам пасти на памет да продужимо дуж AC и BD, и дуплирамо их (инспирација из АB=2\overline{CD}), и тада ћемо због Талесове теореме добити да је услову задатка еквивалентан услов да се те две дужи секу у истој тачки (покушајте да докажете, здраво је и забавно). Ова тачка је слика тачке A у односу на C и тачке B у односу на D. Како је N<1500, природно је размишљати у смеру решења с квадратном сложеношћу, те и посматрања свака два пара тачака. Уколико за сваке две тачке X,Y памтимо све тачке које се добијају као слика X у односу на Y, видимо да тачка која се појављује k пута одређује \binom{k}{2}=\frac{k*(k+1)}{2} сумњивих четвороуглова, те за сваку упамћену тачку треба сабрати ову вредност. Ово је могуће имплементирати сортирањем слика тачака представљених као пар бројева (координата) и бројањем појављивања сваке.