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 ≤ 10⁹
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).

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 Dispozitiv:

/*
    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;
}

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 #1246 Dispozitiv

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1246 Dispozitiv 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 #1246 Dispozitiv