Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <cstdio>
- #include <string>
- #include <algorithm>
- using namespace std;
- typedef struct rectangle{
- int width,height;
- bool horizontal,vertical,placed,first_placed_vertical,first_placed_horizontal;
- int urc [2],ulc[2],brc[2],blc[2];
- }Rectangle;
- typedef struct point{
- int x,y,visited;
- }Point;
- bool check_intersection(Rectangle *array_rec,vector<Point> &possible_points,Point toplace,int rec,int orientation);
- bool place_rectangle(Rectangle *array_rec,vector<Point> &possible_points,Point toplace,int rec);
- int n_rectangles=0; /*nº de rectangulos no input*/
- long total_height=0,total_width=0;
- long area=0;
- bool solution(Rectangle *array_rec,vector<Rectangle> &array_col,int*solutions, long* area,vector<Point> &possible_points,vector <Point> &removed_points,int rec);
- int main() {
- int solutions=0;
- Rectangle* array_rec=new Rectangle[n_rectangles]; /* array que guarda as medidas de cada rectangulo*/
- vector<Rectangle> array_col;
- vector <Point> possible_points;
- vector <Point> removed_points;
- scanf("%d",&n_rectangles);
- for(int i=0;i<n_rectangles;i++){
- fscanf(stdin,"%d %d",&array_rec[i].width,&array_rec[i].height);
- array_rec[i].placed=false;
- array_rec[i].first_placed_vertical=false;
- array_rec[i].first_placed_horizontal=false;
- area += (array_rec[i].width * array_rec[i].height);
- }
- printf("Área Total:%ld\n",area);
- solution(array_rec,array_col,&solutions,&area,possible_points,removed_points,0);
- printf("%d",solutions);
- return 0;
- }
- void vertical_coordinates(Rectangle *array_rec,int sq,int blcx,int blcy) {
- array_rec[sq].blc[0] = blcx;
- array_rec[sq].blc[1] = blcy;
- array_rec[sq].brc[0] = blcx+array_rec[sq].width;
- array_rec[sq].brc[1] = blcy;
- array_rec[sq].ulc[0] = blcx;
- array_rec[sq].ulc[1] = blcy+array_rec[sq].height;
- array_rec[sq].urc[0] = blcx+array_rec[sq].width;
- array_rec[sq].urc[1] = blcy+array_rec[sq].height;
- }
- void horizontal_coordinates(Rectangle *array_rec,int sq,int blcx,int blcy) {
- array_rec[sq].blc[0] = blcx;
- array_rec[sq].blc[1] = blcy;
- array_rec[sq].brc[0] = blcx+array_rec[sq].height;
- array_rec[sq].brc[1] = blcy;
- array_rec[sq].ulc[0] = blcx;
- array_rec[sq].ulc[1] = blcy+array_rec[sq].width;
- array_rec[sq].urc[0] = blcx+array_rec[sq].height;
- array_rec[sq].urc[1] = blcy+array_rec[sq].width;
- }
- bool accept_solution(Rectangle* array_rec){
- for(int i=0;i<n_rectangles;i++){
- if(!array_rec[i].placed){
- return false;
- }
- }
- return true;
- }
- bool place_rectangle(Rectangle *array_rec,vector<Point> &possible_points,Point toplace,int rec){
- for(int x =0; x<(int)possible_points.size();x++){
- if (possible_points[x].x==toplace.x && possible_points[x].y==toplace.y){
- possible_points[x].visited+=1;
- }
- }
- toplace.visited+=1;
- printf("Rectangulo: %d\n",rec);
- Rectangle aux_rec=array_rec[rec];
- vertical_coordinates(array_rec, rec, toplace.x, toplace.y);
- printf("To Place: %d %d\n", toplace.x, toplace.y);
- if(check_intersection(array_rec,possible_points,toplace,rec,0)) {
- Point ulc = {array_rec[rec].ulc[0], array_rec[rec].ulc[1],0};
- Point brc = {array_rec[rec].brc[0], array_rec[rec].brc[1],0};
- printf("Point ulc: %d %d Point brc: %d %d \n", ulc.x, ulc.y, brc.x, brc.y);
- possible_points.push_back(ulc);
- possible_points.push_back(brc);
- for(int s=0;s<(int)possible_points.size();s++){
- if(possible_points[s].x==toplace.x && possible_points[s].y==toplace.y){
- possible_points.erase(possible_points.begin()+s);
- }
- }
- return true;
- }
- else {
- printf("rodou\n");
- printf("To Place Horiz: %d %d\n", toplace.x, toplace.y);
- horizontal_coordinates(array_rec,rec,toplace.x,toplace.y);
- if(check_intersection(array_rec,possible_points,toplace,rec,1)){
- Point ulc = {array_rec[rec].ulc[0], array_rec[rec].ulc[1],0};
- Point brc = {array_rec[rec].brc[0], array_rec[rec].brc[1],0};
- printf("Point ulc: %d %d Point brc: %d %d \n", ulc.x, ulc.y, brc.x, brc.y);
- possible_points.push_back(ulc);
- possible_points.push_back(brc);
- for(int s=0;s<(int)possible_points.size();s++){
- if(possible_points[s].x==toplace.x && possible_points[s].y==toplace.y){
- possible_points.erase(possible_points.begin()+s);
- }
- }
- return true;
- }
- array_rec[rec]=aux_rec;
- return false;
- }
- }
- bool check_intersection(Rectangle *array_rec,vector<Point> &possible_points,Point toplace,int rec,int orientation){ /* orientation: 0 vertical 1 horizontal*/
- for (int i = 0; i < (int) possible_points.size(); i++) {
- if(orientation==0) {
- if (toplace.x + array_rec[rec].width < possible_points[i].x && toplace.y + array_rec[rec].height < possible_points[i].y) {
- printf("false intercestion\n");
- return false;
- }
- }
- else{
- if (toplace.x + array_rec[rec].height < possible_points[i].x && toplace.y + array_rec[rec].width < possible_points[i].y) {
- printf("false intercestion\n");
- return false;
- }
- }
- }
- long auxtotal_width=total_width;
- long auxtotal_height=total_height;
- if(total_height<array_rec[rec].ulc[1]){
- auxtotal_height=array_rec[rec].ulc[1];
- }
- if(total_width<array_rec[rec].brc[0]) {
- auxtotal_width =array_rec[rec].brc[0];
- }
- printf("w %ld h %ld\n",auxtotal_width,auxtotal_height);
- if((auxtotal_width)*auxtotal_height<=area){
- total_width=auxtotal_width;
- total_height=auxtotal_height;
- return true;
- }
- else{
- printf("false area \n");
- return false;
- }
- }
- bool check_all_placed(Rectangle *array_rec){
- int placed=0;
- for(int i=0;i<n_rectangles;i++){
- if(array_rec[i].placed){
- placed++;
- }
- }
- if(placed==n_rectangles){
- return true;
- }
- else{
- return false;
- }
- }
- bool all_rectangle_tested(Point point,vector<Rectangle> &array_col){
- printf("Visitados do ponto %d %d: %d\n",point.x,point.y,point.visited);
- if(point.visited==(n_rectangles-(int)array_col.size())){
- printf("ALL TESTED TRUE %d %d\n",point.x,point.y);
- return true;
- }
- printf("ALL FALSE %d %d\n",point.x,point.y);
- return false;
- }
- bool solution(Rectangle *array_rec,vector<Rectangle> &array_col,int*solutions, long* area,vector<Point> &possible_points,vector <Point> &removed_points,int rec){
- if(check_all_placed(array_rec)){ /*Solução encontrada*/
- *solutions+=1;
- possible_points.clear(); /*Reset */
- array_col.clear();
- for(int r=0;r<n_rectangles;r++){
- array_rec[r].placed=false;
- }
- for(int j=0;j<n_rectangles;j++){
- if(!array_rec[j].first_placed_vertical){
- array_rec[j].first_placed_vertical=true;
- printf("chamou func 0\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,j);
- }
- }
- return false;
- }
- if(rec==n_rectangles){
- rec=0;
- printf("chamou func 2\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec);
- }
- if(array_rec[rec].placed){
- printf("chamou func 3\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec+1);
- }
- if(possible_points.empty()){
- Point point={0,0};
- place_rectangle(array_rec,possible_points,point,rec);
- array_rec[rec].placed=true;
- array_col.push_back(array_rec[rec]);
- printf("chamou func 4\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec+1);
- }
- else{
- int processed_points=0;
- for(int i=0;i<(int)possible_points.size();i++){
- if(place_rectangle(array_rec,possible_points,possible_points[i],rec)){
- array_rec[rec].placed=true;
- array_col.push_back(array_rec[rec]);
- printf("chamou func 5\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec+1);
- }
- else{
- processed_points++;
- if(all_rectangle_tested(possible_points[i],array_col)){
- removed_points.push_back(possible_points[i]);
- possible_points.erase(possible_points.begin()+i);
- array_rec[rec].placed=false;
- printf("chamou func 6\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec);
- }
- }
- }
- if(processed_points==(int)possible_points.size()){
- for(int l=0;l<(int)removed_points.size();l++) {
- if (array_rec[rec].blc[0]==removed_points[l].x && array_rec[rec].blc[1]==removed_points[l].y && array_rec[rec].placed){
- if(!all_rectangle_tested(removed_points[l],array_col)){
- printf("TODOS TESTADOS NO PONTO %d %d\n",removed_points[l].x,removed_points[l].y);
- possible_points.push_back(removed_points[l]);
- }
- }
- }
- for(int k=0;k<n_rectangles;k++){
- if(array_rec[k].blc==array_col.back().blc){
- array_rec[k].placed=false;
- }
- }
- array_col.pop_back();
- printf("chamou func 7\n");
- return solution(array_rec,array_col,solutions,area,possible_points,removed_points,rec);
- }
- }
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement