# PBinfo #1246 – Dispozitiv – Rezolvare C++

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

## Enunț

Specificul insulelor din arhipelagul  Maldive (Oceanul Indian) este faptul că toate cele N insule ale sale au forma unui triunghi. Localizarea acestor insule folosește coordonatele carteziene ale celor trei vârfuri.

Administrația acestor insule dorește să instaleze un dispozitiv de emisie-recepţie pe apă sau pe o insulă, într-un punct având coordonate numere naturale (xD, yD), ce transmite semnale numai pe direcții orizontale și verticale concomitent, cu următoarele proprietăţi:


notând cu NRO numărul de insule la care ajunge semnalul pe orizontală și cu NRV numărul de insule la care ajunge semnalul pe verticală, suma NRO + NRV trebuie să fie maximă;
dacă există mai multe puncte cu proprietatea anterioară, atunci se va alege punctul cel mai mic în ordine lexicografică.

Cerința
Să se scrie un program care cunoscând numărul de insule N şi coordonatele carteziene ale vârfurilor acestora, determină coordonatele xD și yD cu proprietățile din enunţ.

Date de intrare
Fișierul de intrare dispozitiv.in conține pe prima linie numărul N, cu semnificaţia de mai sus, iar pe următoarele N linii se află câte şase numere reprezentând coordonatele vârfurilor insulelor (x1 y1 x2 y2 x3 y3).

Date de ieșire
Fișierul de ieșire dispozitiv.out va conține pe prima linie coordonatele xD și yD cu proprietatea din enunţ, separate printr-un spațiu.

Restricții și precizări

1 ≤  N ≤ 10 000
Coordonatele vârfurilor insulelor sunt numere naturale  ≤ 109
Orice două insule nu au puncte comune
Punctul de coordonate (x1, y1) este mai mic decât punctul de coordonate (x2, y2), dacă x1 < x2 sau (x1 = x2 și y1 < y2)

Exemplu:
dispozitiv.in

6
0 7 4 7 1 10
5 1 6 1 6 2
2 3 2 4 4 4
2 0 1 2 4 2
6 7 7 7 6 10
5 0 7 0 7 1
dispozitiv.out

2 1
Explicație
Codificăm insulele cu 1, 2, …, 6, iar insula i va avea coordonatele vârfurilor pe linia i + 1.
Paralelele la axa Ox și Oy prin punctul de coordonate (2, 1) intersectează un număr de NRO = 3 triunghiuri și anume: 4, 2, 6 pe orizontală şi intersectează un număr de NRV = 3 triunghiuri:  4, 3, 1 pe verticală. NRO + NRV este maxim.
Mai sunt și alte puncte cu aceeași proprietate, dar mai mari în ordine lexicografică, cum ar fi punctul de coordonate (6, 1).

## Cod sursă C++

```cpp
/*
	prof. Constantin Galatan
	O(m * log m)
	100 puncte
*/
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("dispozitiv.in");
ofstream fout("dispozitiv.out");
struct Entry { // capat de interval (stanga sau dreapta)
    int x;
    int sgn;  // +1 capat stanga, -1 capat dreapta
    bool operator < (const Entry& p) const {
        return x < p.x || (x == p.x && sgn > p.sgn);
    }
};
int n;
std::vector<Entry> X, Y;
int main()
{
	int x1, y1, x2, y2, x3, y3, xmin, xmax, ymin, ymax, px, py;
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        fin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        xmin = min(x1, min(x2, x3));
        xmax = max(x1, max(x2, x3));
		X.push_back({xmin, +1});
        X.push_back({xmax, -1});
        ymin = min(y1, min(y2, y3));
        ymax = max(y1, max(y2, y3));
        Y.push_back({ymin, +1});
        Y.push_back({ymax, -1});
    }
    sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
    int cnt(0), cmax1(0), cmax2(0);
    for (const auto& p : X)
    {
		cnt += p.sgn;
        if (p.sgn == 1 && cnt > cmax1)
        {
			cmax1 = cnt;
			px = p.x;
		}
    }
    cnt = 0;
    for (const auto& p : Y)
    {
		cnt += p.sgn;
        if (p.sgn == 1 && cnt > cmax2)
        {
			cmax2 = cnt;
			py = p.x;
		}
    }
	fout << px << ' ' << py << '\n';
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

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