# PBinfo #749 – Cerc2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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ța
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 cerc2.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 distincte p1[1], p2[i] 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 cerc2.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 și precizări

1 ≤ N ≤ 5000
0 ≤ M < 125000
1 ≤ p1[i] < p2[i] ≤ N, numere naturale, oricare i din {1,…, M}
NU există perechi p1[i] p2[i] identice.

Exemplu:
cerc2.in

5 6
1 2
1 3
1 4
2 4
3 5
4 5
cerc2.out

3
Explicație
S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figura de mai jos).

## Cod sursă C++

```cpp
program cerc;
const nmax=500;mmax=nmax*(nmax-3)div 2;
      fi='cerc2.in';fo='cerc2.out';
type segm=record p1,p2,lung:integer
          end;
var n,j:integer;m,i:longint;
    p,l:array[0..nmax]of longint;
    ind:array[1..mmax]of longint;
    per:array[1..mmax]of segm;
    s:segm;inters:longint;
    f:text;
procedure calc(var s:segm);
var aux:integer;
begin
  if s.p2-s.p1<=n+s.p1-s.p2 then s.lung:=s.p2-s.p1-1
  else begin
     s.lung:=n+s.p1-s.p2-1;
     aux:=s.p1;s.p1:=s.p2;s.p2:=aux
  end
end;
procedure citire;
var i:longint;
begin
     assign(f,fi);reset(f);
     readln(f,n,m);
     i:=0;
     while not seekeof(f) do begin
         readln(f,s.p1,s.p2);
         calc(s);
         if s.lung=0 then continue;
         inc(p[s.p1]);inc(p[s.p2]);
         inc(l[s.lung]);
         i:=i+1;per[i]:=s
     end;
     m:=i;
     close(f);
end;
procedure sort;
var i,j:longint;
begin
     for i:=2 to n do l[i]:=l[i]+l[i-1];
     for j:=1 to m do begin
         i:=per[j].lung;
         ind[l[i]]:=j;
         dec(l[i])
     end
end;
begin
     citire;
     sort;
     {for i:=1 to m do ind[i]:=i;}
     inters:=0;
     for i:=1 to m do begin
       s:=per[ind[i]];
       j:=s.p1 mod n+1;
       while j<>s.p2 do begin
             inters:=(inters+p[j])mod 1000000;
             j:=j mod n+1
       end;
       dec(p[s.p1]);dec(p[s.p2])
     end;
     assign(f,fo);rewrite(f);
     writeln(f,inters);
     close(f)
end.
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/749)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/749/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-749/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)