Fişierul intrare/ieşire:cerc4.in, cerc4.outSursăLot Juniori 2009 - Baraj 4
AutorRodica PinteaAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.15 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cerc4

N puncte numerotate de la 1 la N sunt aşezate pe cerc, în sensul acelor de ceasornic, în ordine strict crescătoare.
Există M segmente de dreaptă diferite care unesc M perechi de puncte dintre cele N date. Cele două puncte care formează orice pereche sunt distincte.
Distanţele dintre două puncte succesive sunt alese astfel încât să nu existe 3 sau mai multe segmente care trec printr-un acelaşi punct interior cercului.

Cerinţă

Cunoscându-se numărul de puncte, numărul de perechi şi perechile de puncte care vor fi unite, se cere să se determine numărul P de puncte de intersecţie formate de acestea în interiorul cercului (punctele de intersecţie aflate chiar pe cerc nefiind luate în considerare).

Date de intrare

Fişierul de intrare cerc4.in conţine:

  • pe prima linie două numere N şi M despărţite printr-un spaţiu, numere reprezentând numărul de puncte şi respectiv numărul de segmente
  • pe următoarele M linii, câte o pereche de numere dinstincte pi1, pi2 despărţite prin câte un spaţiu, numere reprezentând capetele câte unui segment

Date de ieşire

Fişierul de ieşire cerc4.out va conţine un singur număr P reprezentând numărul total de puncte de intersecţie formate în interiorul cercului. Dacă acest număr depăşeşte 999999, atunci se va scrie numărul format numai din ultimele sale 6 cifre.

Restricţii

  • 1 ≤ N ≤ 500
  • 0 ≤ M ≤ 125000
  • 1 ≤ pi1 ≤ pi2 ≤ N
  • Nu exista doua perechi pi1 pi2 identice

Exemplu

cerc4.incerc4.out
5 6
1 2
1 3
1 4
2 4
3 5
4 5
3

Explicaţie

S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figură) 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?