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

cerc2.out

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cerc2:

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.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #749 Cerc2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #749 Cerc2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #749 Cerc2