== include(page="template/taskheader" task_id="cerc4") ==
Poveste şi cerinţă...
$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.
h2. 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).
h2. Date de intrare
Fişierul de intrare $cerc4.in$ ...
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 $p{~i1~}$, $p{~i2~}$ despărţite prin câte un spaţiu, numere reprezentând capetele câte unui segment
h2. Date de ieşire
În fişierul de ieşire $cerc4.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 500$
* $0 ≤ M ≤ 125000$
* $1 ≤ p{~i1~} ≤ p{~i2~} ≤ N$
* Nu exista doua perechi $p{~i1~}$ $p{~i2~}$ identice
h2. Exemplu
table(example). |_. cerc4.in |_. cerc4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6
1 2
1 3
1 4
2 4
3 5
4 5
| 3
|
h3. Explicaţie
...
S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figură)
!problema/cerc4?cerc.jpg!
== include(page="template/taskfooter" task_id="cerc4") ==
