Clasa a XII-a
Ziua 2
Problema 4

Acoperire

Intr-un sistem ortogonal de coordonate xOy se dau p (1<=p<=5000) puncte distincte de coordonate x,y din N (1<=x,y<=255). Sa se determine pozitia unui dreptunghi de dimensiuni m si n (1<=m,n<=100, m,n din N) cu laturile paralele cu axele de coordonate care cuprinde in interior si pe frontiera un numar maxim din punctele date.

Fisierul de intrare input.txt are forma:
m n - dimensiunile dreptunghiului
p - numarul de puncte
x₁  y₁ - coordonatele celor p puncte
x₂ y₂
. . .
x_p y_p

Fisierul de iesire output.txt va avea forma:
k - numarul de puncte cuprinse īn interiorul si pe frontiera dreptunghiului
u v - coordonatele (intregi) ale coltului din stānga-jos al dreptunghiului
x₁ y₁ - coordonatele celor k puncte cuprinse in dreptunghi
x₂ y₂
. . .
x_k y_k

Exemplu
Pentru fisierul de intrare "input.txt" ce contine:
3 2
6
3 3
4 2
2 3
2 1
5 4
1 5
fisierul de iesire "output.txt" poate contine:
4
2 2
3 3
4 2
2 3
5 4

Nota: Daca exista mai multe solutii se va afisa una singura.

Timp de executie maxim: 4 secunde pe test.

Punctaj maxim posibil: 75 puncte