== include(page="template/taskheader" task_id="civilizatie") ==

Poveste şi cerinţă...

În vremuri străvechi Pământul era locuit de către o civilizaţie neobişnuită condusă după reguli matematice foarte riguroase. Această civilizaţie era formată din mai multe oraşe stat asemeni oraşelor antice. Fiecare oraş s-a dezvoltat treptat pornind de la un singur cartier de formă pătrată cu suprafaţa de un hectar, în jurul căruia se adăugau în fiecare an cartiere de câte un hectar fiecare în felul următor: în primul an s-a format cartierul iniţial, în al doilea an oraşul s-a extins formând patru noi cartiere în toate cele patru puncte cardinale, în anul următor oraşul s-a extins cu 8 noi cartiere dispuse în jurul cartierelor deja formate, şi aşa mai departe, în fiecare an oraşul extinzându-se cu încă un rând de cartiere.
 
 
!problema/civilizatie?146135151462678.jpg!
 
 

h2. Cerinţe

h2. Date de intrare

Fişierul de intrare $civilizatie.in$ ...

Fişierul de intrare $civilizatie.in$ conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, $p$ poate avea doar valoarea $1$ sau valoarea $2$.
A doua linie a fişierului conţine două numere naturale $x$ şi $y$ reprezentând dimensiunile hărţii.
A treia linie a fişierului conţine numărul natural $t$.
A patra linie a fişierului conţine numărul natural $N$.
Pe următoarele $N$ linii se găsesc câte două numere $i$ şi $j$ reprezentând coordonatele iniţiale ale celor $N$ oraşe.

h2. Date de ieşire

În fişierul de ieşire $civilizatie.out$ ...

Dacă valoarea lui $p$ este $1$, atunci se va rezolva numai prima cerinţă.
În acest caz, în fişierul de ieşire $civilizatie.out$ se va scrie un singur număr natural, reprezentând aria suprafeţei (în hectare) unui oraş după $t$ ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
Dacă valoarea lui $p$ este $2$ atunci, se va rezolva numai a doua cerinţă.
În acest caz, fişierul de ieşire va conţine pe prima linie un număr natural reprezentând aria suprafeţei din hartă rămasă neocupată după ce toate cele $N$ oraşe şi-au încetat expansiunea, iar pe a doua linie un număr natural reprezentând timpul scurs până când ultimul oraş s-a oprit din expansiune.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 2.000$
* $1 ≤ x, y, t ≤ 100.000$
* $Pentru 30% din teste se garantează faptul că x, y ≤ 500$
* $Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 80 de puncte.$

h2. Exemplu

table(example). |_. civilizatie.in |_. civilizatie.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. civilizatie.in |_. civilizatie.out |_. Explicaţie |
|1
 7 9
 9
 2
 3 2
 4 6
| 145
| p = 1, în fişier se va scrie aria suprafeţei ce ar putea fi
  ocupată de un oraş în timp de 9 ani.
  *Atenţie! Pentru acest test se rezolvă doar cerinţa 1).*

|

h3. Explicaţie

table(example). |_. civilizatie.in |_. civilizatie.out |_. Explicaţie |
| 2
  7 9
  5
  2
  3 2
  4 6
| 33
  4
| p=2, deci se rezolvă doar cerinţa 2
|
 
table(example). |_. civilizatie.in |_. civilizatie.out |_. Explicaţie |
|2
 10 10
 5
 3
 2 2
 2 4
 3 2
|97
 1
| p=2, deci se rezolvă doar cerinţa 2
  În acest caz, cele 3 civilizaţii nu se vor putea extinde deloc, deci celelalte 97 de                  hectare rămân neocupate.
|

...

== include(page="template/taskfooter" task_id="civilizatie") ==