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ă.

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.

#include <bits/stdc++.h>


#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;
}