Rezolvare PBinfo #1246

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