Fişierul intrare/ieşire:plagiat.in, plagiat.outSursăAlgoritmiada 2014, Runda 2
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Plagiat

Giani, un Mai Mare al Oraşului, este acuzat de plagiat în lucrarea sa de licenţă intitulată "Despre cromatica semnelor de circulaţie". S-a format, bineînţeles, o comisie care să decidă asupra veridicităţii acestei acuzaţii. Aceasta este formată dintr-un semn de circulaţie, un cetăţean care se ocupă cu trafic de fier vechi, un delfin şi un cetăţean care citeşte în stele. În această problemă ne vom preocupa de metoda prin care se va decide cititorul în stele. Acesta se va uita la harta cerului, formată din N stele punctiforme. Apoi va lua în considerare toate triunghiurile care se pot forma cu vârfurile în stele, iar dacă găseşte două triunghiuri astfel încât primul poate fi obţinut din al doilea doar printr-o translaţie atunci consideră că acesta este un semn, iar Giani este vinovat.

Dându-se T hărţi ale cerului, să se decidă pentru fiecare dacă Giani este vinovat de plagiat sau nu.

Date de intrare

Fişierul de intrare plagiat.in conţine pe prima sa linie T, numărul de hărţi pe care trebuie să le analizaţi. Fiecare hartă va fi descrisă printr-un număr N, numărul de stele, şi N perechi de numere naturale care descriu coordonatele stelelor.

Date de ieşire

În fişierul de ieşire plagiat.out se vor afla T linii. Linia cu numărul i va conţine cuvântul "DA" dacă Giani este vinovat conform hărţii cu numărul i din input. Altfel va conţine cuvântul "NU".

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 400
  • Coordonatele stelelor se află în intervalul [0, 109]
  • Nu vor exista două stele cu aceleaşi coordonate.

Exemplu

plagiat.inplagiat.out
2
5
1 1
2 2
1 2
0 0
100 105
5
1 1
2 2
1 2
0 0
0 1
NU
DA

Explicaţie

În primul caz Giani este absolvit de orice vină, toate triunghiurile posibile fiind distincte relativ la translaţii.
În cel de al doilea caz, triunghiurile (1, 2, 3) respectiv (1, 4, 5) se pot obţine unul din altul prin translaţii. În acest caz Giani îşi pune speranţele în votul delfinului.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content