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:

lub w drugą stronę:

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,y_p,y_k). Przy wyznaczaniu krawędzi musimy znaleźć najmniejszą i największą wartość współrzędnej y. Dla naszego przykładu jest to:

Zerujemy pole S i rozpoczynamy "przeglądanie" linią poziomą. Wybieramy prostą równoległą do osi OX o współrzędnej y = y_min. 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 y_p i y < y_k. 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 x₁ i x₂ i dodajemy do S różnicę (x₂ - x₁). 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 y_max 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 ⁿ/₂.
2. Jak rozpoznać w danych wejściowych krawędź pionową? Otóż ustalamy punkt startowy na x₁ = 0 i y₁ = 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 = x₁ oraz dla N y_p = y₁, y_k = y₁ + liczba lub dla S y_k = y₁, y_p = y₁ - liczba. Krawędź wstawiamy na listę krawędzi (może to być zwykła tablica). Punkt x₁, y₁ modyfikujemy następnie zgodnie z odczytanym kierunkiem ruchu (N: zwiększa y₁ o liczbą, S: zmniejsza y₁ o liczbę, E: zwiększa x₁ o liczbę, W: zmniejsza x₁ o liczbę). Liczba punktów przecięć krawędzi z prostą może maksymalnie być równa liczbie krawędzi prostopadłych, czyli ⁿ/₂.
3. W trakcie odczytu danych wejściowych wyznaczamy y_min i y_max.

// 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 y_k. W trakcie wyszukiwania punktów przecięć prostej z krawędziami pomijamy, te, których współrzędne y_k 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.