Rezolvare completă PbInfo #1819 Copaci

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 ≤ 500
  • 2 ≤ 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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Copaci:

#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("copaci.in");
ofstream g("copaci.out");

int n,m,x,y,i,j,k,dmax,v[250002];
int main()
{
  f>>m>>n>>k;
  j=-1;
  for(i=1;i<=k;i++)
  {
      f>>x>>y;
      v[++j]=(y-1)*m+x;
  }
  for (i=0;i<j-1;i++)
    for (k=i+1;k<j;k++)
  if(v[i]>v[k])
    {
        int aux=v[i];v[i]=v[k];v[k]=aux;
    }
  (v,v+j);
  dmax=0;
  for(i=1;i<j;i++)
    if (v[i]-v[i-1]>dmax)dmax=v[i]-v[i-1];
  if (dmax) g<<dmax-1<<'\n';
  else g<<dmax<<'\n';
  for(i=1;i<j;i++)
    if (v[i]-v[i-1]==dmax)
    {
        x=v[i-1]%m;
        y=v[i-1]/m+1;
        g<<x<<' '<<y<<' ';
        x=v[i]%m;
        y=v[i]/m+1;
        g<<x<<' '<<y<<'\n';
    }
  f.close();
  g.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1819 Copaci

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1819 Copaci de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!