Fişierul intrare/ieşire:triunghiuri2.in, triunghiuri2.outSursăOJI 2017 clasa a 8-a
AutorAlin BurtaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Triunghiuri2 (clasa a 8-a)

Notă: problema este punctată uşor diferit faţă de original din cauza restricţiilor impuse de evaluatorul infoarena.

Se consideră N puncte din plan, având coordonate numere naturale, relativ la un reper cartezian XOY, oricare două puncte fiind distincte.

Cerinţă

Cunoscând N şi coordonatele celor N puncte, să se determine:

  1. Numărul maxim de puncte care au aceeaşi abscisă.
  2. Numărul triunghiurilor care se pot desena respectând următoarele condiţii:
  • au toate vârfurile în puncte dintre cele date;
  • au o latură paralelă cu OX;
  • nu au laturi paralele cu OY;

Date de intrare

Datele de intrare se citesc din fişierul triunghiuri2.in, care are următoarea structură:

  • Pe prima linie se află numărul p, care indică cerinţa ce trebuie rezolvată (p are valoarea 1 sau 2);
  • Pe a doua linie se află numărul natural N, reprezentând numărul punctelor date;
  • Pe următoarele N linii se găsesc câte două valori naturale x y, separate prin câte un spaţiu, reprezentând coordonatele punctelor date.

Date de ieşire

Fişierul triunghiuri2.out va avea următoarea structură:

  • Dacă p = 1 se va scrie în fişier, pe prima linie, numărul maxim de puncte care au aceeaşi abscisă (cerinţa 1).
  • Dacă p = 2 se va scrie în fişier, pe prima linie, numărul triunghiurilor care se pot desena respectând condiţiile date, modulo 1 000 003, adică restul împărţirii numărului de triunghiuri la 1 000 003 (cerinţa 2).

Restricţii

  • 3 ≤ N ≤ 100 000
  • 0 ≤ x < 1000
  • 0 ≤ y < 1000
  • Se acordă 10 puncte din oficiu, 25 30 puncte pentru rezolvarea corectă a cerinţei 1 şi 65 70 puncte pentru rezolvarea corectă a cerinţei 2.

Exemple

triunghiuri2.intriunghiuri2.outExplicaţie
1
5
2 1
1 4
3 4
3 2
6 4
2
Se rezolvă cerinţa 1).
Sunt maximum două puncte care au aceeaşi abscisă , (3, 4) şi (3,2)
2
5
2 1
1 4
3 4
3 2
6 4
4
Se rezolvă cerinţa 2).
Se pot trasa 4 triunghiuri care satisfac cerinţele.
Dacă notăm cele 5 puncte din fişier cu A, B, C, D, E (ca în imagine),
atunci, cele 4 triunghiuri care satisfac cerinţele sunt : ABC, ACE, ABE şi BDE.
Trebuie sa te autentifici pentru a trimite solutii. Click aici