Pe un teren dreptunghiular de dimensiuni m şi n, din loc în loc sunt plantaţi copaci. Pentru fiecare copac se cunosc rândul şi coloana pe care este plantat, între ei fiind spaţii neplantate. Doi copaci se consideră consecutivi dacă mergând pe coloane, numai de la nord către sud, între ei sunt doar spaţii neplantate.
Cerința
Să se determine cea mai mare distanţă dintre doi copaci consecutivi şi toate perechile de copaci între care există această distanţă.
Date de intrare
Fişierul copaci.in conţine pe prima linie, m, n si k (m numărul de randuri, n numărul de coloane şi k numărul de copaci), separate prin cate un spaţiu; pe fiecare dintre următoarele k linii, câte o pereche de numere x, y (separate prin cate un spaţiu) reprezentând rândul, respectiv coloana pe care se află un copac.
Date de ieșire
Fişierul copaci.out va conţine pe prima linie distanţa maximă dintre doi copaci consecutivi, iar pe fiecare dintre următoarele linii câte patru numere întregi x1, y1, x2, y2 (separate prin cate un spaţiu), reprezentând coordonatele (rândul şi coloana) a doi copaci consecutivi între care distanţa este maximă.
Observaţii
- Distanţa dintre dintre doi copaci consecutivi este dată de numărul de spaţii neplantate dintre ei.
- Dacă sunt mai multe perechi de copaci între care distanţa este maximă acestea se vor afişa în ordinea crescătoare a numărului de coloană.
Restricții și precizări
1 < m,n ≤ 5002 ≤ k ≤ 10000
Exemplul 1:
copaci.in
3 4 2 2 4 3 4
copaci.out
0 2 4 3 4
Explicație
Sunt 2 copaci plantaţi pe coloana a 4-a şi între ei nu se află nici un spaţiu neplantat.
Exemplul 2:
copaci.in
6 7 7 1 1 1 4 2 6 3 3 4 2 5 4 6 3
copaci.out
8 1 1 4 2 5 4 2 6
Explicație
Sunt 7 copaci. Distanţa maximă între 2 copaci consecutivi este egală cu 8.
Pe un teren dreptunghiular de dimensiuni m şi n, din loc în loc sunt plantaţi copaci. Pentru fiecare copac se cunosc rândul şi coloana pe care este plantat, între ei fiind spaţii neplantate. Doi copaci se consideră consecutivi dacă mergând pe coloane, numai de la nord către sud, între ei sunt doar spaţii neplantate.
Cerința
Să se determine cea mai mare distanţă dintre doi copaci consecutivi şi toate perechile de copaci între care există această distanţă.
Date de intrare
Fişierul copaci.in conţine pe prima linie, m, n si k (m numărul de randuri, n numărul de coloane şi k numărul de copaci), separate prin cate un spaţiu; pe fiecare dintre următoarele k linii, câte o pereche de numere x, y (separate prin cate un spaţiu) reprezentând rândul, respectiv coloana pe care se află un copac.
Date de ieșire
Fişierul copaci.out va conţine pe prima linie distanţa maximă dintre doi copaci consecutivi, iar pe fiecare dintre următoarele linii câte patru numere întregi x1, y1, x2, y2 (separate prin cate un spaţiu), reprezentând coordonatele (rândul şi coloana) a doi copaci consecutivi între care distanţa este maximă.
Observaţii
- Distanţa dintre dintre doi copaci consecutivi este dată de numărul de spaţii neplantate dintre ei.
- Dacă sunt mai multe perechi de copaci între care distanţa este maximă acestea se vor afişa în ordinea crescătoare a numărului de coloană.
Restricții și precizări
1 < m,n ≤ 5002 ≤ k ≤ 10000
Exemplul 1:
copaci.in
3 4 2 2 4 3 4
copaci.out
0 2 4 3 4
Explicație
Sunt 2 copaci plantaţi pe coloana a 4-a şi între ei nu se află nici un spaţiu neplantat.
Exemplul 2:
copaci.in
6 7 7 1 1 1 4 2 6 3 3 4 2 5 4 6 3
copaci.out
8 1 1 4 2 5 4 2 6
Explicație
Sunt 7 copaci. Distanţa maximă între 2 copaci consecutivi este egală cu 8.
Sunt 2 perechi de copaci care se află la această distanţă. Prima pereche are copacii pe coloanele 1 respectiv 2, a doua pereche are copacii pe coloanele 4 respectiv 6.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("copaci.in");
ofstream cout("copaci.out");
bool a[501][501];
int main()
{
int n , m , p , x , y , l = 0 , lmax = -1 , st = -1;
cin >> n >> m >> p;
for(int i = 0 ; i < p ; ++i)
{
cin >> x >> y;
a[x][y] = 1;
}
for(int j = 1 ; j <= m ; ++j)
for(int i = 1 ; i <= n ; ++i)
{
if(a[i][j] == 1)
{
if(l > lmax && st != -1) lmax = l;
st = a[i][j];
l = 0;
}
if(a[i][j] == 0)l++;
}
st=-1;
cout << lmax << endl;
int dr = 0;
for(int j = 1 ; j <= m ; ++j)
for(int i = 1 ; i <= n ; ++i)
{
if(a[i][j]==1)
{
if(l == lmax && st != -1)
cout << dr << ' ' << st << ' ' << i << ' ' << j << endl;
st = j , dr = i;
l = 0;
}
if(a[i][j]==0) l++;
}
return 0;
}
