Wyznaczanie części wspólnej 2 prostokątów (współrzędne)

Question

Hej, mam do zrobienia takie zadanie. 

Wiersze szachownicy ponumerowane są od dołu ku górze, od 1 do n, zas kolumny –  ́ od lewej do prawej: od 1 do m. Zatem kazde pole na planszy ma dobrze określone  współrzędne (x, y), gdzie x oznacza numer kolumny, zas ́ y – numer wiersza. Pola na szachownicy pokolorowane są na czarno/biało. Pole (1,1) jest zamalowane na biało.

Na takiej szachownicy można określić położenie  ̇prostokąta (a, b, c, d) – jego lewy dolny róg ma współrzędne: (a, b), zaś prawy górny:  (c, d). Najpierw rozlała si  ̨e biała farba i pokryła dokładnie prostokąt (x1, y1, x2, y2), następnie wylała si  ̨e farba czarna jednolicie na prostokąt (x3, y3, x4, y4). Jesli obydwa prostokąty  ́
miały część wspólną, to w wyniku tego zajścia będzie ona miała kolor czarny.

Na wejściu dostajemy wymiary całej planszy oraz najpierw współrzędne  rogów prostokąta białego a następnie współrzędne prostokąta czarnego. 

Należy wypisać ile ostatecznie będzie pól koloru białego a ile będzie pól koloru czarnego. 

Napisałem część kodu która oblicza ile jest pól białych a ile czarnych na początku oraz ile jest pól białych a ile czarnych po wylaniu białej farby. Mam problem z wyznaczeniem części wspólnej tych prostokątów. Wklejam swój kod, jeśli byłyby jakieś pytania co do treści to piszcie bo starałem się skrócić bo zadanie opisane przez autorów ma z 2 strony. 

#include <cstdio>
#include <iostream>
using namespace std;
int k,w; //kolumny wiersze
int b,c; //ilość pól białych na początku
int kb,wb,kb2, wb2; //kolumny biale, wiersze białe
int kc,wc,kc2,wc2; //kolumny czarne, wiersze czarne

int ilePolBialych(int x, int y, int czyBiale) //czy białe mówi o tym czy prostokąt zaczyna się od koloru białego
{
    int z;
    if(x%2!=0 and y%2!=0)
    {
        z=(x*y+czyBiale)/2;
        return z;
    }else
    {
        z=x*y/2;
        return z;
    }
}

int ilePolCzarnych(int x, int y, int czyBiale){
    return x*y-ilePolBialych( x, y, czyBiale);
}

int i;
int main()
{
b=0;
c=0;
//cin>>k>>w;
k=8;w=8;
b=ilePolBialych(k, w,1);
c=(k*w)-b;
cout<<b<<endl<<c<<endl;
//cin>>kb>>wb>>kb2>>wb2;

kb=1;
wb=1;
kb2=3;
wb2=3;
i=ilePolCzarnych(kb2-kb+1,wb2-wb+1,(kb+wb+1)%2);
b=b+i;
c=c-i;
cout<<b<<endl<<c;

return 0;}

Pozdrawiam i z góry dzięki za pomoc

Answer 1

Napisałem taki kod:

#include <iostream>

using namespace std;

int height, width;
int num_black, num_white; //number of black/white tiles
int x1_black, y1_black, x2_black, y2_black, x1_white, y1_white, x2_white, y2_white; //x1, y1 - bottom left corner, x2, y2 - top right corner
int x1_inter, y1_inter, x2_inter, y2_inter; //coordinates of intersection

int cntTiles(int h, int w) //count number of tiles of the same colour as the tile in bottom left corner
{
    return (h*w+1)/2;
}

int main()
{
    cin >> height >> width;
    cin >> x1_white >> y1_white >> x2_white >> y2_white;
    cin >> x1_black >> y1_black >> x2_black >> y2_black;

    num_white = cntTiles(height, width);
    num_black = height*width - num_white;

    //white block
    int change = cntTiles(x2_white-x1_white+1, y2_white-y1_white+1);

    if(x1_white % 2 != y1_white % 2) //bottom left tile is black
    {
        num_black -= change;
        num_white += change;
    }

    else //bottom left tile is white
    {
        num_black -= (x2_white-x1_white+1)*(y2_white-y1_white+1) - change;
        num_white += (x2_white-x1_white+1)*(y2_white-y1_white+1) - change;
    }

    //black block
    change = cntTiles(x2_black-x1_black+1, y2_black-y1_black+1);

    if(x1_black % 2 != y1_black % 2) //bottom left tile is black
    {
        num_black += (x2_black-x1_black+1)*(y2_black-y1_black+1) - change;
        num_white -= (x2_black-x1_black+1)*(y2_black-y1_black+1) - change;
    }

    else //bottom left tile is white
    {
        num_black += change;
        num_white -= change;
    }
    
    //intersection of white and black block
    x1_inter = max(x1_white, x1_black);
    x2_inter = min(x2_white, x2_black);
    y1_inter = max(y1_white, y1_black);
    y2_inter = min(y2_white, y2_black);

    if(x1_inter <= x2_inter && y1_inter <= y2_inter)
    {
        change = cntTiles(x2_inter-x1_inter+1, y2_inter-y1_inter+1);

        if(x1_inter % 2 != y1_inter % 2)
        {
            num_black += change;
            num_white -= change;
        }

        else
        {
            num_black += (x2_inter-x1_inter+1)*(y2_inter-y1_inter+1) - change;
            num_white -= (x2_inter-x1_inter+1)*(y2_inter-y1_inter+1) - change;
        }
    }

    cout << "Number of black tiles: " << num_black << "\nNumber of white tiles: " << num_white << "\n";
}

Da się go pewnie trochę skrócić, ale to już sam musiałbyś pokombinować. Ogólnie pomysł jest taki sam jak w Twoim kodzie. Czyli liczymy ile jest czarnych i białych na początku, a potem odpowiednio dodajemy/odejmujemy przy rozlewaniu czarnej i białej farby. A na końcu odpowiednio poprawiamy dla części wspólnej.

Samą część wspólną można obliczyć sposobem opisanym tutaj.

Za długo tego kodu nie testowałem więc mogą być jakieś błędy, aczkolwiek ja żadnych nie znalazłem

Comments

Dzięki wielkie, zobaczę sobie twój kod z ciekawości. Ale posiedziałem wczoraj do późna i ostatecznie udało mi się napisać swój własny kod :D mimo wszystko wielkie dzięki ❤️