Revizia anterioară Revizia următoare
Fișierul intrare/ieșire | cladire.in, cladire.out | Sursă | .campion 2010 |
---|---|---|---|
Autor | Marinel Șerban | Adăugată de | Stefan Pitur • StefanPitur |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Clădire (clasele 7/8)
Vasile și-a cumpărat un teren de formă dreptunghiulară pe care vrea să-și construiască o casă. Din păcate, unele zone din teren sunt fie ocupate cu pomi, fie improprii unei construcții, astfel încât el dorește să determine o zonă cât mai mare din teren pe care să poată să-și construiască casa. Fiecare zonă pe care nu se poate construi are exact dimensiunea 1 × 1. Și mai are un necaz: arhitectul i-a proiectat casa … pătrată. În figura alăturată se vede un exemplu de astfel de teren: are dimensiunile de 6 × 9 și trei zone pe care nu se poate construi (zonele de coordonate (2, 6), (3, 2) și (5, 7)). În figură se observă faptul că cea mai mare zonă pătrată este zona indicată (de la (3, 3) la (6, 6)), deși există zone dreptunghiulare de arie mai mare.
Cerinta
Determinați latura celei mai mari zone de forma unui pătrat existente în terenul lui Vasile, zona pe care se poate construi.
Date de intrare
Fișierul de intrare cladire.in conține pe prima linie dimensiunile m n ale terenului, două numere naturale separate printr-un spațiu. Linia a doua a fișierului de intrare conține un număr natural k, reprezentând numărul de zone pe care nu se poate construi. Următoarele k linii ale fișierului conțin fiecare câte două numere naturale x y, separate printr-un spațiu, reprezentând fiecare coordonatele unei astfel de zone.
Date de ieșire
Fișierul de ieșire cladire.out conține pe prima linie un singur număr natural L, reprezentând lungimea laturii celei mai mari zone de formă pătrată pe care se poate construi care se găsește pe terenul lui Vasile.
Restricții
- 0 < m, n < 1001
- 0 ≤ k < m*n
- Numerotarea liniilor și coloanelor se face de la 1.
Exemplu
cladire.in | cladire.out |
---|---|
6 9
3
2 6
3 2
5 7 |
4 |