Program liczący pole części wspólnej dwóch prostokątów

Odpowiedz Nowy wątek
2011-10-21 15:57

Rejestracja: 8 lat temu

Ostatnio: 6 miesięcy temu

0

Witajcie mam problem z tym zadaniem

Każdy prostokąt o bokach równoległych do osi układu współrzędnych na płaszczyźnie jest określony przez 2 punkty: lewy górny i prawy dolny. Dane są dwa prostokąty A i B. Ich parametry (8 liczb całkowitych) użytkownik podaje w inicjacji odpowiednich zmiennych. Policzyć pole części wspólnej A, B.

Pozostało 580 znaków

bo
2011-10-21 17:20
bo
0

Weź kartkę papieru, narysuj i zobaczysz jak liczyć to pole. Część wspólna też jest prostokątem.

Pozostało 580 znaków

2011-10-21 17:30

Rejestracja: 8 lat temu

Ostatnio: 6 miesięcy temu

0

Narysowałem, ale nic mi to nie pomaga. Wiem jak obliczyć pole jednego prostokąta ale nie przychodzi mi pomysł na część wspólną

No to pomyśl nieco dłużej. Programowanie polega na logicznym myśleniu i próbowaniu znalezienia rozwiązania ;) - Patryk27 2011-10-21 17:39

Pozostało 580 znaków

2011-10-21 17:45

Rejestracja: 8 lat temu

Ostatnio: 6 miesięcy temu

0

To po co jest forum gdzie ludzie sobie nawzajem pomagają. Jakbym wiedział jak to zrobić to bym nie pisał. Cały czas się zastanawiam i nie potrafię nic sensownego wymyślić, dlatego proszę o pomoc a zamiast tego dostaję dobre rady w stylu nie wiesz jak to pomyśl

Bo po co szukać i stracić 5 minut swojego życia, skoro można zadać pytanie na forum, prawda? - Patryk27 2011-10-21 21:28

Pozostało 580 znaków

2011-10-21 19:28

Rejestracja: 16 lat temu

Ostatnio: 1 miesiąc temu

0

Ja bym to zrobił tak:

  1. Sprawdzenie czy prostokąty mają część wspólną - test czy którykolwiek punkt narożnika prostokąta A(Pa1, Pa2) zawiera się wewnąrz prostokąta B(Pb1, Pb2).
  2. Jeżeli tak, to załóżmy że oznaczamy:
    • Na(nax, nay) -punkt narożnika prostokąta A zawierający się wewnąrz prostokąta B.
  3. Szukamy narożnika prostokąta B(Pb1, Pb2) zawierającego się w wewnąrz prostokąta A(Pa1, Pa2).
    • Nb(nbx, nby)

Zakładamy że:
X - długość boku prostokąta wynikowego C rownoległa do osi x,
Y - długość boku prostokąta wynikowego C rownoległa do osi y,

  1. Obliczamy X = Abs(nbx - nax), Y = Abs(nby - nay)
  2. Obliczamy pole prostokata C: p = X * Y

Może są inne sposoby policzenia tego, ale to pierwszy pomysł jaki mi wpadł do głowy ...

edytowany 1x, ostatnio: zibicoder, 2011-10-21 19:39

Pozostało 580 znaków

2011-10-22 02:54

Rejestracja: 11 lat temu

Ostatnio: 1 rok temu

Lokalizacja: Polska, Warszawa

0

Może by jednak nie wymyślać na nowo koła?
Pomysł z definiowaniem prostokątów przez ich wierzchołki jest średni. Przede wszystkim dlatego, że potem trzeba bawić się w odejmowanie 1 lub dekrementowanie wartości tymczasowych. A Java ma przecież wygodną definicję prostokąta i większość potrzebnych operacji.

    //wersja dla leniwych lemurów
    Point a1, a2, b1, b2;
    //...
    Rectangle a = new Rectangle(a1, new Dimension(Math.abs(a2.x - a1.x), Math.abs(a2.y - a1.y)));
    Rectangle b = new Rectangle(b1, new Dimension(Math.abs(b2.x - b1.x), Math.abs(b2.y - b1.y)));
    Rectangle c = a.intersection(b);
    final int area = c.isEmpty()? 0 : c.width * c.height;

Wersja dla pracowitych zawiera własną metodę części wspólnej opierającą się na minimalizowaniu odcinków składających się na boki prostokąta wspólnego (współrzędne lewego-górnego rogu się maksymalizuje, a prawego-dolnego minimalizuje). Wywołanie intersectionArea(a,b) daje wynik liczbowy.

    //wersja dla pracowitych mrówek
    private class Rect
    {
        public Rect(final Point a, final Point b)
            throws IllegalArgumentException
        {
            if(!(a.x <= b.x && a.y <= b.y))
                throw new IllegalArgumentException(
                    "left-upper corner coordinates is not preceding"
                    + " right right-bottom corner coordinates ");
            this.a = a;
            this.b = b;
        }

        public long area()
        {
            final int width = Math.abs(b.x - a.x);
            final int height = Math.abs(b.y - a.y);
            return width * height;
        }

        private final Point a, b;
    }

    private Rect intersection(final Rect r1, final Rect r2)
        throws IllegalArgumentException
    {
        Point ia = new Point();
        ia.x = Math.max(r1.a.x, r2.a.x);
        ia.y = Math.max(r1.a.y, r2.a.y);
        Point ib = new Point();
        ib.x = Math.min(r1.b.x, r2.b.x);
        ib.y = Math.min(r1.b.y, r2.b.y);
        return new Rect(ia, ib);
    }

    private long intersectionArea(Rect a, Rect b)
    {
        Rect result = null;
        try { result = intersection(a, b); }
        catch(IllegalArgumentException ignore) { return 0; }
        return result.area();
    }

Jeżeli ktoś komuś coś, ewentualnie nikt nikomu nic, to właściwie po co...?
edytowany 6x, ostatnio: Olamagato, 2011-10-23 23:19

Pozostało 580 znaków

2011-10-22 09:17

Rejestracja: 15 lat temu

Ostatnio: 1 miesiąc temu

0

w skrócie, jest to iloczyn różnic gdzie różnicę liczymy tak: max(a-b, 0)

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0