Se consideră N puncte din plan, având coordonate numere naturale, relativ la un reper cartezian XOY, oricare două puncte fiind distincte.

Cerința

Cunoscând N și coordonatele celor N puncte, să se determine:

1) Numărul maxim de puncte care au aceeași abscisă.
2) Numărul triunghiurilor care se pot desena respectând următoarele condiții:

• au toate vârfurile în puncte dintre cele date;
• au o latură paralelă cu OX;
• nu au laturi paralele cu OY;

Date de intrare

Fișierul de intrare triunghiuri2.in conține pe prima linie numărul p, care indică cerința ce trebuie rezolvată (p are valoarea 1 sau 2). Pe a doua linie se află numărul natural N, reprezentând numărul punctelor date. Pe următoarele N linii se găsesc câte două valori naturale x y, separate prin câte un spațiu, reprezentând coordonatele punctelor date.

Date de ieșire

Fișierul triunghiuri2.out va avea următoarea structură:

• Dacă p = 1 se va scrie în fișier, pe prima linie, numărul maxim de puncte care au aceeași abscisă (cerința 1).
• Dacă p = 2 se va scrie în fișier, pe prima linie, numărul triunghiurilor care se pot desena respectând condițiile date, modulo 1 000 003, adică restul împărțirii numărului de triunghiuri la 1 000 003 (cerința 2).

Restricții și precizări

• 3 <= N <= 100 000
• 0 <= x < 1000
• 0 <= y < 1000
• Se acordă 25 puncte pentru rezolvarea corectă a cerinței 1 și 65 puncte pentru rezolvarea corectă a cerinței 2. În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

triunghiuri2.in

1
5
2 1
1 4
3 4
3 2
6 4

triunghiuri2.out

2

Explicație

Se rezolvă cerința 1). Sunt maximum două puncte care au aceeași abscisă: (3, 4) și (3,2).

Exemplul 2

triunghiuri2.in

2
5
2 1
1 4
3 4
3 2
6 4

triunghiuri2.out

4

Explicație

Se rezolvă cerința 2). Se pot trasa 4 triunghiuri care satisfac cerințele. Dacă notăm cele 5 puncte din fișier cu A, B, C, D, E (ca în imagine), atunci, cele 4 triunghiuri care satisfac cerințele sunt : ABC, ACE, ABE și BDE.

Autor prof.  Alin Burța

Colegiul Național  “B.P. Hasdeu” Buzău

Solutie de complexitate O(n)

Cerința 2

Considerăm  vectorii nx și ny cu semnificația:

nx [i] = numărul punctelor care au abscisa egală cu i;

ny[i] = numărul punctelor care au ordonata egală cu i;

Valorile celor doi vectori pot fi calculate incă de la citirea coordonatelor punctelor. În același timp memorăm , pentru fiecare ordonată y între 0 și 999, lista absciselor punctelor care au ordonata egală cu y, obținînd un tablou bidimensional H (H[i][j] – al j-lea punct din lista punctelor de ordonată i).

Numărul triunghiurilor cu proprietatea cerută se calculează astfel:

Pentru fiecare ordonată i din plan, pentru care numărul punctelor de pe aceasta este cel puțin egal cu 2, calculăm cîte triunghiuri se pot forma avînd două puncte cu ordonata egală cu i și al treilea punct de ordonată diferită de i.

Pentru aceasta vom scădea din numărul total de triunghiuri care se pot forma (cu o latură paralelă cu OX, aflată pe dreapta y = i) numarul triunghiurilor cu o latură paralelă cu OY, adică

( N – ny[i]) * ( ny[i] * (ny[i] – 1) / 2 ) – sumTrParaleleOY

Valoarea sumTrParaleleOY se calculează luând fiecare punct de ordonată i și contorizând câte triunghiuri dreptunghice cu un vârf în acel punct se pot forma, adică:

sumTrParaleleOY = 0;

for(j = 1; j <= ny[i]; ++j) sumTrParaleleOY += ( nx[ H[i][j] ] – 1 ) * (ny[i] – 1);

Algoritmul va parcurge practic toată lista de puncte astfel că ordinul său de complexitate este O(n).

///prof. Cristina Sichim
#include <fstream>
#include <vector>
#define MOD 1000003

using namespace std;
ifstream fin("triunghiuri2.in");
ofstream fout("triunghiuri2.out");

int x[1005],n,v,i,a,b,k;
long long t, aux1, aux2, aux,aux3;
vector <int> Y[1005];
vector <int> :: iterator it;
int main()
{ fin>>v>>n;
  for(i=1;i<=n;++i)
  { fin>>a>>b;
    x[a]++;
    Y[b].push_back(a);
  }
  if(v==1) {a=x[0];
            for(i=0;i<=999;++i) if(x[i]>a)a=x[i];
            fout<<a<<'\n';
           }
  else
    { for(i=0;i<=999;++i)
        { k=Y[i].size();
          if(k>=2)
          {
              aux1=n-k;
              aux2=k*(k-1)/2;
              aux=aux1*aux2;

              for(it=Y[i].begin();it!=Y[i].end();++it)
              {
                      aux3=x[*it]-1;
                      aux3=aux3*(k-1);
                      aux=aux-aux3;
              }

            t=(t+aux)%MOD;
          }
        }
      fout<<t<<'\n';
    }
    fin.close();fout.close();
    return 0;
}

///sursa oficiala - prof. Alin Burta
#include <fstream>

#define Nmax 100001         //numarul maxim de puncte
#define Cmax 1001           //coordonata maxima
#define IN "triunghiuri2.in"
#define OU "triunghiuri2.out"

using namespace std;

long N;                     //numarul punctelor
long long NrTr;                  //numarul triunghiurilor gasite

short nx[Cmax];             // nx[i] - cate puncte sunt pe absisa i
short ny[Cmax];             // ny[i] - cate puncte sunt pe ordonata i
short H[Cmax][Cmax];        //memorez punctele ordonate  H[i] - lista punctelor cu ordonata i

long long aux, aux1, aux2,  sumLin;

int main()
{
    long int i, j, Max, V;
    short x, y;
    //citire date
    ifstream Fin(IN);
    Fin >> V >> N;
    for(i = 0; i <= Cmax - 1; ++i) nx[i] = ny[i] = 0;
    for(i = 1; i <= N; ++i)
    {
        Fin >> x >> y;
        nx[x]++; ny[y]++;
        H[ y ][ ny[y] ] = x;
    }
    Fin.close();

    if( V == 1)
    {
        Max = 0;
        for(i = 0; i <= 999; ++i)
            if(nx[i] > Max)
                Max = nx[i];
        ofstream Fou(OU);
        Fou << Max << '\n';
        Fou.close();
    }
    else
    {
        NrTr = 0;
        for( i = 0; i< Cmax-1; ++i)
        if(ny[i] > 1)
        {
            sumLin = 0;
            for(j = 1; j<=  ny[i]; ++j) sumLin +=  ( nx[ H[i][j] ] - 1 ) * (ny[i] - 1);
            aux1 = ( ny[i] * (ny[i] - 1) / 2 );
            aux2 = ( N - ny[i]);
            aux = aux1 * aux2;
            NrTr +=  aux  - sumLin ;
            NrTr %= 1000003;
        }
        ofstream Fou(OU);
        Fou << NrTr << '\n';
        Fou.close();
    }
    return 0;
}