Fişierul intrare/ieşire:dispozitiv.in, dispozitiv.outSursăLot IV Juniori 2015
AutorDoru Popescu AnastasiuAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Dispozitiv (Lot Juniori)

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-radio-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ţă

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

  • 1 ≤ N ≤ 10 000
  • Coordonatele vârfurilor insulelor sunt numere naturale ≤ 1 000 000 000
  • 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.indispozitiv.outExplicaţie
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
2 1
Codificăm insulele cu 1, 2, …, 6, iar insula i va avea cordonatele
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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici