Question

Prosiłabym o napisanie algorytmu do zadania. Z objaśnieniem wszystkiego.

http://main.edu.pl/en/user.phtml?op=showtask&task=mal&con=PA2012

Answer 1

 

Robisz tablicę dwuwymiarową typu int, która reprezentować będzie pomalowaną scianę. Każda komórka tej tablicy będzie przechowywać liczbę, która będzie mówić o tym ile razy dany kawałek został pomalowany.

.

Na wejściu masz liczbę dzieci, będzie to głowna pętla for, dla każdej iteracji tej pętli czytasz wiersz danych będacych współrzednymi zamalowanego kawałka (x1,y1,x2,y2). Następne "malujemy ścianę" czyli pętla for(int i = x1; i < x2 ; i++) for(int j = y1 ; j< y2 ; j++) tab[i][j]++;

.

Pętle te przechodzą tablice w zależności od podanego rozmiaru kawałka pomalowanej ściany i zwiększa liczbę mówiąca o tym ile razy dany kawałek ściany został pomalowany.

.

Na końcu musisz zliczyć dobre kawałki, czyli takie które pozostały pomalowane N-1 razy (N liczba dzieci). Robisz to przechodząc normalnie przez tablice i sprawdzając czy tab[i][j] większe bądź równe N-1 jeśli tak to inkrementujesz jakąś zmienna np wynik++

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Answer 2

Rozwiązanie polega na policzeniu dla kazdego prostokata, czesci wspolnej wszystkich prostokatow oprócz danego Można to zrobić obliczając tablicę prefiksową i sufiksową częsci wspólnych. Dla i-tego prostokąta taką częscią wspólną będzie część wspólna z części wspólnej od 1 do i-1 i częsci wspólnej od i+1 do n.

Następnie należy zsumować pola wszystkich otrzymanych czesci wspólnych i odjęcia n-1 razy części wspólnej tym razem wszystkich już prostokątów.

 

Majac 2 prostokaty o wspolrzednych:(x1,y1,x2,y2) i (x3,y3,x4,y4) częscią wspólną jest (max(x1,x3),(max(y1,y3),min(x2,x4),min(y2,y4))