# PBinfo #153 – drept – Rezolvare C++

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

## Enunț

La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii:
1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale
2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy
3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Cerinţa
Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Date de intrare
Pe prima linie a fişierului de intrare drept.in se află numărul natural N reprezentând numărul de segmente orizontale. Pe următoarele N linii se află câte 3 numere naturale y x1 x2 reprezentând coordonatele segmentelor astfel: y – coordonata verticală (ordonata), x1 şi x2 – coordonatele orizontale (abscisele).

Date de ieşire
Fişierul de ieşire drept.out va conţine un singur număr, reprezentând restul împărţirii numărului total de dreptunghiuri speciale la 946021.

Restricţii şi precizări

1 ≤ N ≤ 50.000
0 ≤ x1≤ x2 ≤ 1.000.000.000
0 ≤ y ≤ 1000
Vârfurile oricărui dreptunghi special sunt distincte două câte două şi nu pot avea toate aceeaşi ordonată
Pentru un număr de teste în valoare de 60 de puncte, N ≤ 5000

Exemple
Exemplul 1 
drept.in

3
2 2 3
1 1 4
3 3 4
drept.out

2
Exemplul 2
drept.in

4
3 1 5
2 2 4
1 2 3
1 2 5
drept.out

12

## Cod sursă C++

```cpp
//autor Adrian Airinei 
//O(YMAX*N)-100 puncte
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 50100
#define MAX_Y 1010
#define MOD 946021
#define PI pair<int, int>
int N, res;
vector< PI > Y[MAX_Y];
void read_data(void)
{
	int i, a, b, y;
	scanf("%d", &N);
	for(i = 1; i <= N; i++)
		scanf("%d %d %d", &y, &a, &b), Y[y].push_back(make_pair(a,b));
}
void normalize(void)
{
	int i, j, k, cnt;
	for(i = 0; i < MAX_Y; i++)
	{
		sort(Y[i].begin(), Y[i].end());
		cnt = 0;
		for(j = 0; j < Y[i].size(); j++)
		{
			k = j;
			while(j+1 < Y[i].size() && Y[i][j+1].first >= Y[i][k].first && Y[i][j+1].first <= Y[i][k].second)
				Y[i][k].second = max(Y[i][k].second, Y[i][j+1].second), j++;
			Y[i][cnt++] = Y[i][k];
		}
		Y[i].resize(cnt);
	}
}
int intersect(PI a, PI b)
{
	if(a.first >= b.first && a.first <= b.second)
		return min(a.second, b.second)-a.first+1;
	if(b.first >= a.first && b.first <= a.second)
		return min(b.second, a.second)-b.first+1;
	return 0;
}
void solve(void)
{
	int i, j, k, indi, indj, r;
	for(i = 0; i < MAX_Y; i++)
		for(j = i+1; j < MAX_Y; j++)
		{
			r = indi = indj = 0;
			while(indi < Y[i].size() && indj < Y[j].size())
			{
				r += intersect(Y[i][indi], Y[j][indj]);
				if(Y[i][indi].second <= Y[j][indj].second)
					indi++;
				else
					indj++;
			}
			res += (int) ( (long long)r*(r-1)/2%MOD );
			res %= MOD;
		}
}
int main(void)
{
	freopen("drept.in", "rt", stdin);
	freopen("drept.out", "wt", stdout);
	read_data();
	normalize();
	solve();
	printf("%d
", res);
	return 0;
}
```

## Resurse

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