castel

Time limit: 0.4s
Memory limit: 32MB
Input: castel.in
Output: castel.out

După ce a scăpat de Spân și a devenit împărat, Harap-Alb a decis să-și construiască un nou castel în împărăția sa ce poate fi reprezentată cu ajutorul sistemului de coordonate carteziene. El știe că Roș-Împărat a construit N+1N+1 garduri dreptunghiulare, însă știe și că acesta este cam zgârcit și nu a folosit cele mai bune materiale.

Harap-Alb a învățat din greșeli, iar acum încearcă să se ferească de pericole cât de mult poate. De aceea, el vrea să își amplaseze castelul într-un punct din sistemul cartezian care să se afle în interiorul a cel puțin NN dintre cele N+1N+1 garduri.

Cerință

Fiind date numărul natural nenul NN și coordonatele celor N+1N+1 garduri (perechi de colțuri stânga-sus și dreapta-jos), să se determine (în cazul în care există) punctul cel mai apropiat de originea sistemului de coordonate unde Harap-Alb își poate amplasa castelul astfel încât acesta să se afle în interiorul a cel puțin NN garduri.

Date de intrare

Fișierul de intrare castel.in conține pe prima linie numărul natural nenul NN, cu semnificația de mai sus. Următoarele N+1N+1 linii conțin câte patru numere naturale aia_i, bib_i, cic_i, did_i, (1iN+1)(1 \leq i \leq N+1), separate între ele prin câte un spațiu, reprezentând coordonatele gardurilor. Colțul din stânga-sus al gardului ii se află în punctul de abscisă aia_i și ordonată bib_i, iar cel din dreapta-jos în punctul de abscisă cic_i și ordonată did_i.

Date de ieșire

Fișierul de ieșire castel.out conține pe prima linie două numere naturale, reprezentând abscisa, respectiv ordonata punctului determinat conform cerinței. Dacă sunt mai multe astfel de puncte, se va alege cel cu abscisa minimă. Dacă nu există niciun astfel de punct, se va afișa mesajul NU.

Restricții și precizări

  • 1N<200 0001 \leq N < 200 \ 000;
  • 0ai0 \leq a_i, bib_i, cic_i, di<100 000d_i < 100 \ 000 și aicia_i \leq c_i, dibid_i \leq b_i, pentru fiecare ii: 1iN+11 \leq i \leq N+1;
  • Laturile tuturor dreptunghiurilor sunt paralele cu axele de coordonate ale sistemului cartezian;
  • Originea sistemului de coordonate se află în punctul (0,0)(0,0);
  • Interiorul unui gard conține și gardul (conturul);
  • Pot exista dreptunghiuri degenerate, adică segmente (paralele cu axele de coordonate) sau puncte;
  • Pot exista dreptunghiuri identice;
  • Distanța dintre două puncte situate la coordonatele (a,b)(a,b), respectiv (c,d)(c,d) este egală cu (ca)2+(db)2\sqrt{(c-a)^2+(d-b)^2}.
# Punctaj Restricții
1 19 N<200N < 200 și ai,bi,ci,di<200a_i,b_i,c_i,d_i < 200, pentru fiecare ii: 1iN+11 \leq i \leq N + 1.
2 30 N<2 000N < 2 \ 000
3 51 Nu există alte restricții suplimentare

Exemplul 1

castel.in

3
1 4 3 2
4 2 5 0
2 3 4 2
2 3 5 1

castel.out

2 2

Explicație

Zona hașurată cu roșu reprezintă punctele ce se află în interiorul a cel puțin 33 dreptunghiuri. Punctul (4,2)(4,2) respectă, de asemenea, cerința. Dintre toate acestea, (2,2)(2,2) este cel mai apropiat de origine.

Exemplul 2

castel.in

4
1 4 5 2
2 5 3 1
4 5 5 1
3 6 4 5
2 5 5 4

castel.out

NU

Explicație

Niciun punct nu se află în interiorul a cel puțin 44 garduri, așa cum se poate observa în diagrama de mai jos.

Problem info

ID: 541

Editors:

Author:

Source: ONI 2023 VIII: Problema 1

Tags:

ONI 2023 VIII

Log in or sign up to be able to send submissions!