PROBLEMA TAIETURILOR:

PROBLEMA TAIETURILOR:Se dau n = numar de gauri pe o o tabla de lungime l si inaltime h si de asemenea coodronatle gaurilor aflate pe tabla. Se cere determinarea unei bucati de tabla de suprafata maxima care nu contine gauri. Se pot realiza taieturi pe orizontala sau verticala prin punctele determinate de coordonatele citite.Ex. fisierul de intrare:2 4 42 11 2Iesire: 2 2 aria 9

Vom avea o tabla de dimensiune 4*4 gaurita prin punctele de coordonate (2,1) si (1,2). Deci, ne putem imagina o matrice cu 4 linii si 4 coloane si la intersectia liniie 2 si coloanei 1 este tabla gaurita, precum si la intersectia liniei 1 cu coloana 2!Daca decupam tabla prin punctul (2,1) se realizeaza o taietura pe verticala, in stanga nu mai ramane nici o bucata de tabla, iar in dreapta ramane o bucata de tabla dreptunghiulara din punctul stanga sus (1,2) in punctul dreapta jos (4,4) care contine o gaura in (1,2), prin care trebuiea sa se realizeze o alta decupare ...etc...Daca decupam tabla prin punctul (2,1) se realizeaza o taietura pe orizontala se obtine deasupra liniie 2 o bucata formata dintr-o linie ce contine gaura si o bucata incepand cu linia 3 alta bucata.Suprafata negaurita de arie maxima va fi, pt, exemplu, de arie 9 , dreptunghiul cu coltul stanga sus (2,2) si dreapta jos (4,4), adica 3 linii si 3 coloane=> aria 3*3=9.Aceasta suprafata s-a obtinut printr-o taitura orizontala in pct (1,2) si apoi in punctul (2,1) al tablei initiale o taietura verticala.

Vom gandi astfel, pentru suprafata cu coltul stanga sus (x,y), lungimea l si inaltimea h v-a tb sa determinam un o bucata de tabla negaurita determinata de (xf,yf) coordonatele finale coltul stanga sus, lf si hf dimensiunile finale ale suprafetei.- mai intai determinap o gaura pe tabla tabla; variabila gasit va avea valoarea 1 daca s-a gasit un astfel de punct:- daca am gasit o gaura, pentru acest punct aplicam taieturile pe orizontala (se obtin doua probleme similare se tb rezolvate la fel; se apleeaza RECURSIV) si la fel si pentru taietura pe verticala se obtin doua probleme similare => 4 apeluri recursive pentru noile suprafete;- Cand s-a terminat de rezolvat problema, adica am gasit supratfata negaurita vom compara ariile bucatilor de tabla negaurita, retinand tabla cu aria maxima!

#include int l, h, i,n, xf,yf, lf, hf;int xv[10], yv[10];void divi (int x,int y,int l,int h, int &xf, int &yf,int &lf, int &hf){ int gasit, i; i=1; gasit=0; while (i=x && xv[i]=y && yv[i]lf*hf) {xf=x; yf=y; lf=l; hf=h;//cout