Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cerc4.in, cerc4.out | Sursă | Lot Juniori 2009 - Baraj 4 |
| Autor | Rodica Pintea | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | cerc4.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
