Koło informatyczne - ciekawe zadanie ACM

1974

Problem A - Górna liga


Opis

HARDFLOR Ic. jest firmą specjalizującą się w wykonywaniu podłóg z lastriko. Pobierana jest opłata od stopy kwadratowej ułożonej podłogi. Firma jest bardzo dobra w wykonywaniu tych podłóg, lecz ma pewien kłopot w obliczaniu powierzchni, ponieważ podłogi występują w wielu kształtach i rozmiarach, np.
 

 

Jedną z reguł, którą stworzył przed laty założyciel firmy, John Hardflor, jest "nigdy nie podejmować się wykonania podłogi bez prostych narożników". Firma wciąż stosuje się do tej reguły. Jednakże dalej mają kłopoty w oszacowaniu powierzchni i chcieliby teraz, aby został dla nich opracowany program, który by ich wspierał w tym przedsięwzięciu.

Firmowy kosztorysant chciałby pojawić się na miejscu potencjalnej pracy i zmierzyć wymiary pokoju, kodując je w sposób następujący:

Np. pewien pokój o poniżej przedstawionych wymiarach:

 

 

mógłby być zakodowany za pomocą następującego zbioru par: [(N,9) (E,16) (N,4) (E,7) (S,13) (W,23)].

Napisz program, który obliczy powierzchnię. Załóż, że kodowanie jest zawsze prawidłowe - zawsze kończy się w tym samym narożniku, od którego się zaczęło.

 

Specyfikacja wejścia

Pierwsza liczba n określa liczbę narożników. Za liczbą narożników występuje n par postaci: litera (N, S, E lub W) liczba.

 

Specyfikacja wyjścia

Dla wczytanego opisu pokoju program powinien wypisać jego powierzchnię w postaci:

 

THE AREA IS 99999

 

Przykładowe dane wejściowe

6 N 9 E 16 N 4 E 7 S 13 W 23

 

Przykładowe dane wyjściowe

THE AREA IS 235

 

Przykładowe rozwiązanie

Problem powyższy można rozwiązać na kilka sposobów. Jednym z nich jest metoda przeglądania liniami poziomymi.

Niech dana będzie podłoga o następującym kształcie:

 

 

Punkt startowy definicji zaznaczyliśmy czerwonym kołkiem. Jeśli założymy następujące kierunki:

 

 

To definicja tej podłogi może wyglądać następująco:

 

18 N 3 E 2 S 2 E 2 N 5 W 5 N 2 W 3 S 5 W 2 N 5 W 2 S 8 E 3 S 2 E 9 N 2 W 4

 

lub w drugą stronę:

 

18 E 4 S 2 W 9 N 2 W 3 N 8 E 2 S 5 E 2 N 5 E 3 S 2 E 5 S 5 W 2 N 2 W 2 S 3

 

W obu przypadkach definiujemy ten sam równoległobok. W wieloboku będą nas interesowały tylko krawędzie pionowe:

 

 

Musimy teraz znaleźć współrzędne tych krawędzi. Jeśli umówimy się, że punkt startowy ma współrzędne (0,0), to otrzymamy:

 

 

Zwróć uwagę, że współrzędna x obu wierzchołków krawędzi jest taka sama, ponieważ krawędź jest zawsze pionowa. Zatem krawędź definiuje jednoznacznie trójka liczb (x,yp,yk). Przy wyznaczaniu krawędzi musimy znaleźć najmniejszą i największą wartość współrzędnej y. Dla naszego przykładu jest to:

 

ymin = -2

ymax = 8

 

Zerujemy pole S i rozpoczynamy "przeglądanie" linią poziomą. Wybieramy prostą równoległą do osi OX o współrzędnej y = ymin. W pętli wyznaczamy punkty przecięcia tej prostej z kolejnymi krawędziami naszego równoległoboku. Umawiamy się, że prosta przecina krawędź, jeśli y yp i y < yk. Zapamiętujemy współrzędne x punktów przecięcia tak, aby były posortowane rosnąco:

 

 

Wyznaczone współrzędne x tworzą listę. Z listy tej bierzemy pary kolejnych współrzędnych x1 i x2 i dodajemy do S różnicę (x2 - x1). Różnica ta jest równa polu paska o szerokości 1 zawartego w naszym równoległoboku:

 

 

Następnie y zwiększamy o 1, co spowoduje podniesienie naszej prostej o 1 w górę. Znów wyznaczamy listę współrzędnych x przecięć tej prostej z krawędziami naszej figury. Z listy bierzemy po dwie współrzędne x i do S dodajemy ich różnicę:

 

 

Prosta wędruje o 1 w górę. Zwróć uwagę, że teraz dwie poprzednie krawędzie nie będą przecinały tej prostej, ponieważ ich współrzędne ymax nie są większe od y.  Otrzymamy zatem nowe punkty x na liście współrzędnych przecięć:

 

 

I dalej:

 

 

 

 

 

 

 

 

Zadanie jest zakończone (kolejne zwiększenie y o 1 spowoduje, że prosta nie przetnie się już z żadną z krawędzi naszej figury). Pole figury wynosi S = 86.

 

Idea podstawowego rozwiązania jest gotowa. jednakże zanim napiszemy gotowy program, musimy rozwiązać kilka podproblemów:

  1. W algorytmie interesują nas jedynie krawędzie pionowe. Zauważ, że z uwagi na kształt figury krawędzie zawsze tworzą pary: krawędź pionowa + krawędź pozioma (lub na odwrót). Zatem liczba krawędzi pionowych jest równa n/2.
  2. Jak rozpoznać w danych wejściowych krawędź pionową? Otóż ustalamy punkt startowy na x1 = 0 i y1 = 0. Następnie odczytujemy parę: kierunek (N, S, W, E) i liczbę. Jeśli odczytany kierunek to N lub S, mamy krawędź pionową. Zapamiętujemy w strukturze krawędzi: x = x1 oraz dla N yp = y1, yk = y1 + liczba lub dla S yk = y1, yp = y1 - liczba. Krawędź wstawiamy na listę krawędzi (może to być zwykła tablica). Punkt x1, y1 modyfikujemy następnie zgodnie z odczytanym kierunkiem ruchu (N: zwiększa y1 o liczbą, S: zmniejsza y1 o liczbę, E: zwiększa x1 o liczbę, W: zmniejsza x1 o liczbę). Liczba punktów przecięć krawędzi z prostą może maksymalnie być równa liczbie krawędzi prostopadłych, czyli n/2.
  3. W trakcie odczytu danych wejściowych wyznaczamy ymin i ymax.
// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// ACM - Pole powierzchni podłogi
// PRG_38
//-----------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

struct edge
{
  int x,yp,yk;
};

int main()
{
  int n;         // liczba wszystkich krawędzi
  int nv;        // liczba krawędzi pionowych
  int ymin,ymax; // minimalna i maksymalna współrzędna y końców krawędzi
  int x1,y1,len; // bieżący punkt
  int y;         // pozycja prostej
  int i,j,k;     // indeksy
  int * VX;      // lista współrzędnych x punktów przecięć krawędzi z prostą
  int S;         // pole figury
  char dir;      // kierunek krawędzi
  edge * VE;     // tablica krawędzi pionowych

  // Odczytujemy liczbę danych do wczytania

  cin >> n;

  // Obliczamy liczbę krawędzi pionowych

  nv = n / 2;

  // Tworzymy dynamiczną tablicę krawędzi

  VE = new edge[nv];

  // Tworzymy dynamiczną tablicę współrzędnych x

  VX = new int[nv];

  // Inicjujemy punkt początkowy

  k = x1 = y1 = ymin = ymax = 0;

  // W pętli odczytujemy dane i tworzymy odpowiednie krawędzie

  for(i = 0; i < n; i++)
  {
    cin >> dir >> len;

    switch(dir)
    {
      case 'E': x1 += len; break;
      case 'W': x1 -= len; break;
      case 'N': VE[k].x    = x1;
                VE[k].yp   = y1;
                VE[k++].yk = (y1 += len);
                break;
      case 'S': VE[k].x    = x1;
                VE[k].yk   = y1;
                VE[k++].yp = (y1 -= len);
                break;
    }

    if(y1 < ymin)      ymin = y1;
    else if(y1 > ymax) ymax = y1;
  }

  // Obliczamy pole figury

  S = 0;

  // W pętli wyszukujemy punkty przecięć prostej z kolejnymi krawędziami.
  // Punkty te składujemy w VX w porządku rosnącym. Znalezione pary
  // punktów wykorzystujemy do przyrostowego obliczania pola figury.

  for(y = ymin; y < ymax; y++)
  {
    k = 0;  // liczba znalezionych punktów przecięć

    // Przeglądamy kolejne krawędzie

    for(i = 0; i < nv; i++)
      if((y >= VE[i].yp) && (y < VE[i].yk))
      {
        for(j = k; j && (VE[i].x < VX[j-1]); j--) VX[j] = VX[j-1];

        VX[j] = VE[i].x;

        k++;
      }

    // Dodajemy różnicę par punktów z VX do S

    for(i = 0; i < k; i += 2) S += VX[i+1] - VX[i];
  }

  // Wyświetlamy wynik

  cout << "THE AREA IS " << S << endl;

  delete [] VE;
  delete [] VX;

  return 0;
}

 

Pierwsza modernizacja może polegać na usprawnieniu przesuwania prostej y. Otóż w trakcie odczytu krawędzi zapamiętujemy współrzędne y wierzchołków początkowych w osobnej tablicy VY w taki sposób, aby były posortowane rosnąco i bez powtórzeń. Zapamiętane wartości posłużą do ustawiania prostej y oraz dadzą nam wysokość prostokątów pola.

 
// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// ACM - Pole powierzchni podłogi
// PRG_39
//-----------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

struct edge
{
  int x,yp,yk;
};

int main()
{
  int n;         // liczba wszystkich krawędzi
  int nv;        // liczba krawędzi pionowych
  int x1,y1,len; // bieżący punkt
  int y;         // pozycja prostej
  int i,j,k;     // indeksy
  int * VX;      // lista współrzędnych x punktów przecięć krawędzi z prostą
  int * VY;      // lista współrzędnych y, na których ma się zatrzymywać prosta
  int ny;        // liczba elementów w VY
  int S;         // pole figury
  char dir;      // kierunek krawędzi
  edge * VE;     // tablica krawędzi pionowych

  // Odczytujemy liczbę danych do wczytania

  cin >> n;

  // Obliczamy liczbę krawędzi pionowych

  nv = n / 2;

  // Tworzymy dynamiczną tablicę krawędzi

  VE = new edge[nv];

  // Tworzymy dynamiczną tablicę współrzędnych x

  VX = new int[nv];

  // Tworzymy dynamiczną tablicę współrzędnych y

  VY = new int [nv + 1];

  // Inicjujemy punkt początkowy

  ny = k = x1 = y1 = 0;

  // W pętli odczytujemy dane i tworzymy odpowiednie krawędzie

  for(i = 0; i < n; i++)
  {
    cin >> dir >> len;

    switch(dir)
    {
      case 'E': x1 += len; break;
      case 'W': x1 -= len; break;
      case 'N': VE[k].x    = x1;
                VE[k].yp   = y1;
                VE[k++].yk = (y1 += len);
                break;
      case 'S': VE[k].x    = x1;
                VE[k].yk   = y1;
                VE[k++].yp = (y1 -= len);
                break;
    }

    // Teraz y1 wstawiamy do VY bez powtórzeń

    bool not_repeated = true;

    for(j = 0; j < ny; j++)
      if(y1 == VY[j])
      {
        not_repeated = false;  // y1 już jest w VY
        break;
      }

    if(not_repeated)
    {
       for(j = ny; j && (y1 < VY[j-1]); j--) VY[j] = VY[j-1];
       VY[j] = y1;
       ny++;
    }
  }

  // Obliczamy pole figury

  S = 0;

  // W pętli wyszukujemy punkty przecięć prostej z kolejnymi krawędziami.
  // Punkty te składujemy w VX w porządku rosnącym. Znalezione pary
  // punktów wykorzystujemy do przyrostowego obliczania pola figury.

  for(y = 0; y < ny - 1; y++)
  {
    k = 0;  // liczba znalezionych punktów przecięć

    // Przeglądamy kolejne krawędzie

    for(i = 0; i < nv; i++)
      if((VY[y] >= VE[i].yp) && (VY[y] < VE[i].yk))
      {
        for(j = k; j && (VE[i].x < VX[j-1]); j--) VX[j] = VX[j-1];
        VX[j] = VE[i].x;
        k++;
      }

    // Dodajemy do S różnicę par z VX pomnożoną przez różnicę
    // współrzędnych y z VY, co daje pole prostokąta pomiędzy kolejnymi
    // pozycjami prostej y, która zatrzymuje się na wierzchołkach krawędzi.

    for(i = 0; i < k; i += 2)
      S += (VX[i+1] - VX[i]) * (VY[y+1] - VY[y]);
  }

  // Wyświetlamy wynik

  cout << "THE AREA IS " << S << endl;

  // Usuwamy tablice dynamiczne
  
  delete [] VE;
  delete [] VX;
  delete [] VY;

  return 0;
}

 

Kolejne ulepszenie może polegać na tym, iż krawędzie składujemy w tablicy VE w porządku rosnących współrzędnych yk. W trakcie wyszukiwania punktów przecięć prostej z krawędziami pomijamy, te, których współrzędne yk są mniejsze lub równe bieżącej współrzędnej prostej. Ponieważ będą to zawsze początkowe krawędzie w VE, to możemy zapamiętywać pozycję, od której należy te krawędzie testować – pozycja ta będzie rosła w miarę odrzucania krawędzi, które już nie mogą tworzyć przecięć z prostą. Dzięki temu program nie będzie sprawdzał wszystkich krawędzi za każdym obiegiem pętli. Modyfikację programu pozostawiam zdolniejszym czytelnikom.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.