Fişierul intrare/ieşire:	fandoseala.in, fandoseala.out	Sursă	Marcel
Autor	Alexandru Petrescu	Adăugată de	Alexandru Petrescu •alexpetrescu
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Fandoseala

Marcel a dat peste un set de N puncte de coordonate naturale X_i şi Y_i cu proprietatile ca nu exista 2 puncte identice, 3 puncte coliniare sau 4 puncte conciclice. Pacat ca Marcel e fandosit si foarte pretentios, mai ales cand vine vorba de un set de puncte asa de bine ales. El vrea sa gasiti 3 indici 1 ≤ a < b < c ≤ N astfel incat cercul determinat de punctele X_a, Y_a; X_b, Y_b; X_c, Y_c sa contina in interior sau pe contur exact K puncte dintre cele date.

Date de intrare

Fişierul de intrare fandoseala.in contine pe prima linie numarul de teste T. Fiecare test are pe prima linie numerele N si K, iar pe urmatoarele N linii perechile de numere naturale X_i şi Y_i.

Date de ieşire

În fişierul de ieşire fandoseala.out se vor afla fix T linii. Pe fiecare linie vor fi afisate cate 3 numere, a, b si c, o solutie pentru testul corespunzator. Daca a = b = c = 0, se va considera ca rezolvarea testului a fost omisa.

Punctare

Evaluarea se va face utilizand 2 fisiere de test. Ambele vor avea 1 ≤ N ≤ 300 si punctajul maxim de 50 de puncte, cu sansa la punctaje partiale. In primul fisier de test, 1 ≤ T ≤ 1.200, iar in al doilea 1 ≤ T ≤ 400. Toate coordonatele X_i şi Y_i sunt nenule si mai mici sau egale cu 10.000. Pentru fiecare subtest, daca exista vreun triplet nenul care sa nu respecte conditiile date, punctajul intregii grupe va fi egal cu 0. Altfel, vor fi acordate puncte in functie de numarul de triplete nenule (prin urmare corecte), sa-l notam Q, dupa formula:

Precizare

Se garanteaza ca pentru datele de test exista solutie; 3 ≤ K ≤ N

Exemplu

Explicaţie

• Cercul determinat de punctele cu indici 2, 6, 8 contine in interior punctul cu indicele 7.
• Scorul obtinut pentru exemplu este de 25 de puncte din maximul de 50

Cum se trimit solutii?