Muszę opracować program C dla danego zestawu wartości wejściowych, gdzie opisujemy prostokątną figurę przez swoją granicę, określając punkt wyjścia i serię ruchów w czterech podstawowych kierunkach - jak gdybyśmy mieli wokół formacji wzdłuż jego granicy .
. Wchodzą do każdego ruchu w kierunku (WESN) i długości - "W3" oznacza ruch z bieżącej pozycji trzech kroków West (w lewo).

enter image description here

Postać na rysunku 1 można opisać - począwszy od prawego górnego rogu - jak:

"W 6, S2, W3, S2, E 1, S2, E 2, N 1, E 2, N 1, E 2, N 1, W2, N 1, E 3, S 3, E 1, n 5 ".

Moim problemem jest:

  1. Jaki jest taki kształt zwany geometrią?
  2. Jak mogę obliczyć obszar takiego kształtu? Mam długości wszystkich boków jako W6, S4 itp

Dzięki.

0
Ahsan Ali 15 kwiecień 2021, 21:50

2 odpowiedzi

Najlepsza odpowiedź

Kształt nazywa się poliomino. To specjalny przypadek wielokąt.

Problem znalezienia obszaru można rozwiązać, rozpoczynając w punkcie {X0}} z wielokąta obszarze {X1}}. Następnie rozszerzając obszar przez prostokąt, poruszając poziomo.

Załóżmy, że bieżący punkt to (x,y). Przeprowadzka na wschód przez {X1}} Jednostka oznacza dodanie prostokąta w punktach (x,0) -> (x,y) -> (x + d, y) -> (x + d, 0). Obszar prostokąta to d * y. Podczas ruchu zachodu trzeba odejść prostokąt.

enter image description here

Ostateczny obszar jest dodatni, jeśli spacer jest w prawo lub ujemny, jeśli ścieżka była przeciwna do ruchu wskazówek zegara.

Ta podejście wynika w bardzo prostym programie:

#include <stdio.h>

int main() {
    int x = 0, y = 0, A = 0, d;
    int c;
    while ((c = getchar()) != EOF) { 
        if        (c == 'W' && scanf(" %d", &d) == 1) {
            x += d;
            A += d * y;
        } else if (c == 'E' && scanf(" %d", &d) == 1) {
            x -= d;
            A -= d * y;
        } else if (c == 'N' && scanf(" %d", &d) == 1) {
            y += d;
        } else if (c == 'S' && scanf(" %d", &d) == 1) {
            y -= d;
        }
    }
    if (A < 0) A = -A;
    printf("%d\n", A);
    return 0;
}

W przypadku wejścia z pytania brzmi daje oczekiwaną odpowiedź 33.

1
tstanisl 15 kwiecień 2021, 21:26

Można to nazwać prostoliniowym wielokąta.

Algorytm ogólny do obliczania obszaru dowolnego wielokąta jest:

  • Niech (xo, yo) będzie punktem wyjścia ("O" dla starego).
  • Zainicjuj sumę do zera.
  • Dla każdego ruchu:
    • Oblicz nowy punkt (XN, YN) ("N" dla nowego) z ruchu i starego punktu.
    • add xn • yo-xo • yn do s.
    • Set xo = xn i yo = yn.
  • Obszar wewnątrz wielokąta jest | S | / 2.

Powyższe zakłady, że ostatni ruch zamyka wielokąt, więc ostatni punkt jest punktem wyjścia. Jeśli tak nie, kopia punktu wyjścia powinna zostać zapisana i używana do zakończenia suma z ostatnim punktem.

Wykorzystuje to Sum / Algorytm Chux wskazane.

3
Eric Postpischil 15 kwiecień 2021, 20:03