== include(page="template/taskheader" task_id="perfect2") ==
Se consideră în planul P reperul cartezian xOy cu originea în punctul O.
Fie A mulţimea tuturor punctelor din plan ale căror coordonate sunt numere naturale nenule. Din A se aleg n puncte distincte: A{~1~}, A_2, ..., A_n.
Denumim segment perfect un segment de dreaptă care uneşte două puncte distincte din mulţimea A şi care nu conţine în interiorul său niciun alt punct din A. De exemplu, segmentul ce uneşte punctele de coordonate (1,4) şi (5,3) este un segment perfect, iar segmentul ce uneşte punctele de coordonate (1,5) şi (5,3) nu este un segment perfect deoarece conţine în interiorul său punctul de coordonate (3,4).
Se consideră în planul $P$ reperul cartezian xOy cu originea în punctul $O$.
Fie $A$ mulţimea tuturor punctelor din plan ale căror coordonate sunt numere naturale nenule. Din $A$ se aleg n puncte distincte: A{~1~}, A{~2~}, ..., A{~n~}.
Denumim segment perfect un segment de dreaptă care uneşte două puncte distincte din mulţimea $A$ şi care nu conţine în interiorul său niciun alt punct din $A$. De exemplu, segmentul ce uneşte punctele de coordonate (1,4) şi (5,3) este un segment perfect, iar segmentul ce uneşte punctele de coordonate (1,5) şi (5,3) nu este un segment perfect deoarece conţine în interiorul său punctul de coordonate (3,4).
h2. Cerinte
Scrieţi un program care să citească numărul natural n şi coordonatele celor n puncte A_1, A_2,...,A_n, şi care să determine:
Scrieţi un program care să citească numărul natural n şi coordonatele celor n puncte A{~1~}, A{~2~},...,A{~n~}, şi care să determine:
1. coordonatele vârfurilor stânga-jos şi dreapta-sus ale dreptunghiului de arie minimă, cu laturile paralele cu axele de coordonate şi care conţine în interiorul său sau pe laturile sale toate cele n puncte;
2. numărul maxim de segmentelor perfecte care pot uni punctul A_1 cu punctele A_2,A_3,...,A_n.
2. numărul maxim de segmentelor perfecte care pot uni punctul A{~1~} cu punctele A{~2~},A{~3~},..., A{~n~}.
h2. Date de intrare
Fişierul de intrare $perfect2.in$ conţine:
* pe prima linie un număr natural p; pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2;
* pe prima linie un număr natural $p$; pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2;
* pe a doua linie, o valoare naturală n reprezentând numărul de puncte alese din mulţimea A;
* pe a doua linie, o valoare naturală $n$ reprezentând numărul de puncte alese din mulţimea $A$;
* pe fiecare din următoarele n linii, câte două numere naturale nenule, separate printr-un singur spaţiu, reprezentând coordonatele(x1,y1) ale punctului A1,..., coordonatele (xn,yn) ale punctului An
* pe fiecare din următoarele $n$ linii, câte două numere naturale nenule, separate printr-un singur spaţiu, reprezentând coordonatele(x1,y1) ale punctului A1,..., coordonatele (xn,yn) ale punctului An
h2. Date de ieşire
Dacă valoarea lui p este 1, atunci se va rezolva numai cerinţa 1.
Dacă valoarea lui $p$ este 1, atunci se va rezolva numai cerinţa 1.
* În acest caz, fişierul de ieşire $perfect2.out$ va conţine pe prima linie patru numere naturale separate prin câte un spaţiu, reprezentând abcisa şi ordonata vârfului stâga-jos, respectiv dreapta-sus (în această ordine) ale dreptunghiului de arie minimă, cu laturile paralele cu axele de coordonate şi care conţine în interiorul său sau pe laturile sale toate cele n puncte reprezentând răspunsul la cerinţa 1.
Dacă valoarea lui p este 2, atunci se va rezolva numai cerinţa 2.
Dacă valoarea lui $p$ este 2, atunci se va rezolva numai cerinţa 2.
* În acest caz, fişierul de ieşire $perfect2.out$ va conţine pe prima linie un număr natural reprezentând numărul maxim de segmente perfecte care pot uni punctul A1 cu punctele A2,A3,...,An reprezentând răspunsul la cerinţa 2.
* În acest caz, fişierul de ieşire $perfect2.out$ va conţine pe prima linie un număr natural reprezentând numărul maxim de segmente perfecte care pot uni punctul A{~1~} cu punctele A{~2~},A{~3~},..., A{~n~} reprezentând răspunsul la cerinţa 2.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $n$ număr natural nenul, 3 ≤ n ≤ 200000
* x{~1~}, x{~2~}, …, x{~n~}, y{~1~}, y{~2~}, …, y{~n~} sunt numere naturale nenule
* 1 ≤ x{~1~}, x{~2~}, …, x{~n~} ≤ 4500 ; 1 ≤ y{~1~}, y{~2~}, …, y{~n~} ≤ 4500
* cel puţin trei puncte din cele $n$ alese nu sunt coliniare
* cele $n$ puncte din plan sunt distincte două câte două
* pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.
h2. Exemplu
table(example). |_. perfect2.in |_. perfect2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
7
8 3
3 1
1 4
5 4
7 2
6 5
4 2
| 1 1 8 5
|
| 2
11
5 3
1 5
1 4
3 4
5 4
6 5
4 2
3 1
7 2
8 3
1 1
| 6
|
h3. Explicaţie
...
* Atentie! Pentru primul exemplu se rezolva doar cerinta 1! Sunt alese 7 puncte: A{~1~}(8,3), A{~2~}(3,1), A{~3~}(1,4), A{~4~}(5,4), A{~5~}(7,2), A{~6~}(6,5), A{~7~}(4,2). Dreptunghiul de arie minimă, cu laturile paralele cu axele de coordonate şi care conţine în interiorul său, sau pe laturile sale, toate cele n puncte are vârful stânga jos de coordonate (1,1) şi vârful dreapta-sus de coordonate (8,5).
* Atentie! Pentru al doilea exemplu se rezolva doar cerinta 2! Sunt alese 11 puncte: A{~1~}(5,3), A{~2~}(1,5), A{~3~}(1,4), A{~4~}(3,4), A{~5~}(5,4), A{~6~}(6,5), A{~7~}(4,2), A{~8~}(3,1), A{~9~}(7,2), A{~10~}(8,3), A{~11~}(1,1). Sunt maximum 6 segmente perfecte ce pot uni punctul A{~1~} cu punctele A{~2~}, A{~3~},..., A{~11~}. Acestea sunt: A{~1~}A{~3~}, A{~1~}A{~4~}, A{~1~}A{~5~}, A{~1~}A{~6~}, A{~1~}A{~7~}, A{~1~}A{~9~}.
Segmentul A{~1~}A{~11~} nu este perfect deoarece conţine punctul de coordonate (3,2). Segmentul A{~1~}A{~10~} nu este perfect deoarece conţine punctele de coordonate (6,3) şi (7,3). Segmentul A{~1~}A{~2~} nu este perfect deoarece conţine punctul A{~4~}. Segmentul A{~1~}A{~8~} nu este perfect deoarece conţine punctul A{~7~}.
== include(page="template/taskfooter" task_id="perfect2") ==
