| Fișierul intrare/ieșire | dispozitiv.in, dispozitiv.out | Sursă | Lot IV Juniori 2015 |
|---|---|---|---|
| Autor | Doru Popescu Anastasiu | Adăugată de |
Tiberiu Musat
•
Tiberiu02
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
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.in | dispozitiv.out | Explicaț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). |
