Fişierul intrare/ieşire:fandoseala.in, fandoseala.outSursăMarcel
AutorAlexandru PetrescuAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Fandoseala

Marcel a dat peste un set de N puncte de coordonate naturale Xi şi Yi 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 Xa, Ya; Xb, Yb; Xc, Yc 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 Xi şi Yi.

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 Xi şi Yi 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:

 [ 50.00 * \frac{Q}{T} ]

Precizare

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

Exemplu

fandoseala.infandoseala.out
2
8 4
5 1
5 2
1 3
1000 1000
2 8
9 6
7 3
9 2
3 3
1 1
2 2
1 3
2 6 8
0 0 0

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?