API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
82
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.28 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef struct rectangle {
  9.     int width,height;/*width->largura | height->comprimento*/
  10.      int urc [2],ulc[2],brc[2],blc[2];
  11.     bool placed;
  12.  
  13. } Rectangle;
  14.  
  15. typedef struct point {
  16.     int x,y;
  17. }Point;
  18.  
  19. int area,total_height,total_width,n_rectangles;
  20. int solutions=0;
  21. pair <Point,Point>  array_sol[100000][8];
  22.  
  23.  
  24. bool check_all_placed(Rectangle *array_rec){
  25.     int placed=0;
  26.     for(int i=0;i<n_rectangles;i++){
  27.         if(array_rec[i].placed){
  28.             placed++;
  29.         }
  30.     }
  31.     //printf("NUM PLACED %d\n",placed);
  32.     if(placed==n_rectangles){
  33.         return true;
  34.     }
  35.     else{
  36.         return false;
  37.     }
  38. }
  39.  
  40. void vertical_coordinates(Rectangle *array_rec,int sq,int blcx,int blcy) {
  41.     array_rec[sq].blc[0] = blcx;
  42.     array_rec[sq].blc[1] = blcy;
  43.     array_rec[sq].brc[0] = blcx+array_rec[sq].width;
  44.     array_rec[sq].brc[1] = blcy;
  45.     array_rec[sq].ulc[0] = blcx;
  46.     array_rec[sq].ulc[1] = blcy+array_rec[sq].height;
  47.     array_rec[sq].urc[0] = blcx+array_rec[sq].width;
  48.     array_rec[sq].urc[1] = blcy+array_rec[sq].height;
  49. }
  50.  
  51. void horizontal_coordinates(Rectangle *array_rec,int sq,int blcx,int blcy) {
  52.     array_rec[sq].blc[0] = blcx;
  53.     array_rec[sq].blc[1] = blcy;
  54.     array_rec[sq].brc[0] = blcx+array_rec[sq].height;
  55.     array_rec[sq].brc[1] = blcy;
  56.     array_rec[sq].ulc[0] = blcx;
  57.     array_rec[sq].ulc[1] = blcy+array_rec[sq].width;
  58.     array_rec[sq].urc[0] = blcx+array_rec[sq].height;
  59.     array_rec[sq].urc[1] = blcy+array_rec[sq].width;
  60. }
  61.  
  62. bool place_rectangle(Rectangle *array_rec,vector<Point> &possible_points,int pos, int rec,int orientation){//pos=posição do ponto no possible point  || 0->vertical 1->horizontal
  63.     Point toplace;
  64.     toplace.x=possible_points[pos].x;
  65.     toplace.y=possible_points[pos].y;
  66.     Point ulc;
  67.     Point brc;
  68.     if (orientation==0){
  69.     vertical_coordinates(array_rec, rec, toplace.x, toplace.y);
  70.     }
  71.     else{
  72.         horizontal_coordinates(array_rec, rec, toplace.x, toplace.y);
  73.     }
  74.     if (toplace.x == 0 && toplace.y==0) {
  75.         possible_points.pop_back();//tirar (0,0)
  76.         total_width = array_rec[rec].width;
  77.         total_height = array_rec[rec].height;
  78.         ulc.x=array_rec[rec].ulc[0];
  79.         ulc.y=array_rec[rec].ulc[1];
  80.         brc.x=array_rec[rec].brc[0];
  81.         brc.y=array_rec[rec].brc[1];
  82.         possible_points.push_back(ulc);
  83.         possible_points.push_back(brc);
  84.         array_rec[rec].placed=true;
  85.         return true;
  86.     }
  87.     else if (toplace.x==0){
  88.        // printf("array rec %d  possible %d",array_rec[rec].brc[0],possible_points[pos+1].x);
  89.         if(array_rec[rec].brc[0]<possible_points[pos+1].x){
  90.             ulc.x=array_rec[rec].ulc[0];
  91.             ulc.y=array_rec[rec].ulc[1];
  92.             brc.x=array_rec[rec].brc[0];
  93.             brc.y=array_rec[rec].brc[1];
  94.             possible_points.erase(possible_points.begin()+pos);
  95.             possible_points.insert(possible_points.begin()+pos,brc);
  96.             possible_points.insert(possible_points.begin()+pos,ulc);
  97.            
  98.             total_height+=array_rec[rec].height;
  99.             return true;
  100.         }
  101.         if(array_rec[rec].brc[0]==possible_points[pos+1].x){
  102.              ulc.x=array_rec[rec].ulc[0];
  103.             ulc.y=array_rec[rec].ulc[1];
  104.             possible_points.erase(possible_points.begin()+pos);
  105.             possible_points.insert(possible_points.begin()+pos,ulc);
  106.             total_height+=array_rec[rec].height;
  107.             return true;
  108.         }
  109.         return false;
  110.     }
  111.     else if (toplace.y==0){
  112.         if(array_rec[rec].ulc[1]<possible_points[pos-1].y){
  113.             ulc.x=array_rec[rec].ulc[0];
  114.         ulc.y=array_rec[rec].ulc[1];
  115.             brc.x=array_rec[rec].brc[0];
  116.             brc.y=array_rec[rec].brc[1];
  117.             possible_points.erase(possible_points.begin()+pos);
  118.             possible_points.insert(possible_points.begin()+pos,brc);
  119.             possible_points.insert(possible_points.begin()+pos,ulc);
  120.             total_width+=array_rec[rec].width;
  121.             return true;
  122.         }
  123.         if(array_rec[rec].ulc[1]==possible_points[pos-1].y){
  124.            brc.x=array_rec[rec].brc[0];
  125.             brc.y=array_rec[rec].brc[1];
  126.             possible_points.erase(possible_points.begin()+pos);
  127.             possible_points.insert(possible_points.begin()+pos,brc);
  128.             total_width+=array_rec[rec].width;
  129.             return true;
  130.         }
  131.         return false;
  132.     }
  133.     if (toplace.x!=0 && toplace.y!=0){
  134.         if(array_rec[rec].ulc[1]<possible_points[pos-1].y && array_rec[rec].brc[0]<possible_points[pos+1].x){
  135.               ulc.x=array_rec[rec].ulc[0];
  136.         ulc.y=array_rec[rec].ulc[1];
  137.             possible_points.insert(possible_points.begin()+pos,brc);
  138.             possible_points.insert(possible_points.begin()+pos,ulc);
  139.             return true;
  140.         }
  141.         if(array_rec[rec].ulc[1]<possible_points[pos-1].y && array_rec[rec].brc[0]==possible_points[pos+1].x){
  142.              ulc.x=array_rec[rec].ulc[0];
  143.         ulc.y=array_rec[rec].ulc[1];
  144.             possible_points.erase(possible_points.begin()+pos);
  145.             possible_points.insert(possible_points.begin()+pos,ulc);
  146.             return true;
  147.         }
  148.         if(array_rec[rec].ulc[1]==possible_points[pos-1].y && array_rec[rec].brc[0]<possible_points[pos+1].x){
  149.             brc.x=array_rec[rec].brc[0];
  150.             brc.y=array_rec[rec].brc[1];
  151.             possible_points.erase(possible_points.begin()+pos);
  152.             possible_points.insert(possible_points.begin()+pos,brc);
  153.             return true;
  154.         }
  155.         if(array_rec[rec].ulc[1]==possible_points[pos-1].y && array_rec[rec].brc[0]==possible_points[pos+1].x){
  156.             possible_points.erase(possible_points.begin()+pos);
  157.             return true;
  158.        
  159.         }
  160.     }
  161.      return false;
  162. }
  163.    
  164. bool compare_Points(const  pair <Point,Point> &p1,const  pair <Point,Point> &p2){
  165.     if(p1.first.x<p2.first.x){
  166.         return true;
  167.     }
  168.     if(p1.first.x>p2.first.x){
  169.         return false;
  170.     }
  171.     if(p1.second.x<p2.second.x){
  172.         return true;
  173.     }
  174.     if(p1.second.x>p2.second.x){
  175.         return false;
  176.     }
  177.     if(p1.first.y<p2.first.y){
  178.         return true;
  179.     }
  180.     if(p1.first.y>p2.first.y){
  181.         return false;
  182.     }
  183.     if(p1.second.y<p2.second.y){
  184.         return true;
  185.     }
  186.     if(p1.second.y>p2.second.y){
  187.         return false;
  188.     }
  189.     return false;
  190. }
  191.  
  192.  
  193. bool solution(Rectangle* array_rec,vector<Point> &possible_points){
  194.  
  195.     if (check_all_placed(array_rec)){
  196.         Point ulc,brc;
  197.         pair <Point,Point> rec_aux;
  198.         if((int)possible_points.size()==2){
  199.             vector<pair <Point,Point> > array_sol_aux;
  200.             for(int i=0;i<n_rectangles;i++){
  201.                
  202.                 ulc.x=array_rec[i].ulc[0];
  203.                 ulc.y=array_rec[i].ulc[1];
  204.                 brc.x=array_rec[i].brc[0];
  205.                 brc.y=array_rec[i].brc[1];
  206.                 rec_aux=make_pair(ulc,brc);
  207.                 array_sol_aux.push_back(rec_aux);
  208.             }
  209.             sort(array_sol_aux.begin(),array_sol_aux.end(),compare_Points);
  210.            
  211.             /*for(int i=0;i<(int)array_sol_aux.size();i++){
  212.                  printf("(%d %d) (%d,%d)\n",array_sol_aux[i].first.x,array_sol_aux[i].first.y,array_sol_aux[i].second.x,array_sol_aux[i].second.y);
  213.             }*/
  214.             if (solutions == 0) {
  215.                     for (int j = 0; j < n_rectangles; j++) {
  216.                         //cout << "VAZIO\n";
  217.                         array_sol[0][j].first.x = array_sol_aux[j].first.x;
  218.                         array_sol[0][j].first.y = array_sol_aux[j].first.y;
  219.                         array_sol[0][j].second.x = array_sol_aux[j].second.x;
  220.                         array_sol[0][j].second.y = array_sol_aux[j].second.y;
  221.                     }
  222.                     solutions++;
  223.                     //printf("##########SOLUTIONS###################\n");
  224.                     return true;
  225.  
  226.                 }else{
  227.                
  228.            
  229.              for (int i = 0; i < solutions; i++) {
  230.                         int igual = 0;
  231.                         for (int j = 0; j < n_rectangles; j++) {
  232.                             //igual=0;
  233.                             if (array_sol[i][j].first.x == array_sol_aux[j].first.x &&
  234.                                 array_sol[i][j].first.y == array_sol_aux[j].first.y &&
  235.                                 array_sol[i][j].second.x == array_sol_aux[j].second.x &&
  236.                                 array_sol[i][j].second.y == array_sol_aux[j].second.y) {
  237.                                 igual++;
  238.                             }
  239.  
  240.                         }
  241.                         if (igual == n_rectangles) {
  242.                             //cout << "igual\n";
  243.                             return false;
  244.                         }
  245.                     }
  246.                     for (int j = 0; j < n_rectangles; j++) {
  247.  
  248.  
  249.                         array_sol[solutions][j].first.x = array_sol_aux[j].first.x;
  250.                         array_sol[solutions][j].first.y = array_sol_aux[j].first.y;
  251.                         array_sol[solutions][j].second.x = array_sol_aux[j].second.x;
  252.                         array_sol[solutions][j].second.y = array_sol_aux[j].second.y;
  253.                     }
  254.  
  255.                
  256.            
  257.             solutions++;
  258.             return true;
  259.                 }
  260.         }
  261.         return false;
  262.        
  263.     }
  264.     else{
  265.             for(int i =0;i<n_rectangles;i++){
  266.                 for(int j=0;j<(int)possible_points.size();j++){
  267.                     vector<Point> possible_points_copy=possible_points;
  268.                     vector<Point> possible_points_copy_horizontal=possible_points;
  269.  
  270.                    if(!array_rec[i].placed){
  271.                         if(place_rectangle(array_rec,possible_points_copy,j,i,0)){
  272.                             //printf("dentro\n");
  273.                             array_rec[i].placed=true;
  274.                             solution(array_rec,possible_points_copy);
  275.                         }
  276.                    
  277.                    if(array_rec[i].width!=array_rec[i].height){
  278.  
  279.                         if(place_rectangle(array_rec,possible_points_copy_horizontal,j,i,1)){
  280.                            // printf("dentro hori\n");
  281.  
  282.                             array_rec[i].placed=true;
  283.                             solution(array_rec,possible_points_copy_horizontal);
  284.                         }
  285.                     }
  286.  
  287.                     array_rec[i].placed=false;
  288.                    }
  289.                 }
  290.             }
  291.  
  292.         }
  293.     return false;
  294. }
  295.  
  296.  
  297.  
  298. int main() {
  299.     Rectangle* array_rec=new Rectangle[n_rectangles]; /* array que guarda as medidas de cada rectangulo*/
  300.     vector <Point> possible_points;
  301.     vector<pair <Point,Point> > array_sol;
  302.     int width,height;
  303.  
  304.     scanf("%d",&n_rectangles);
  305.    
  306.     for(int i=0; i< n_rectangles; i++) {
  307.         scanf("%d %d",&width,&height);
  308.         array_rec[i].width=width;
  309.         array_rec[i].height=height;
  310.         array_rec[i].placed=false;
  311.         area += (array_rec[i].width * array_rec[i].height);
  312.     }
  313.     Point p={0,0};
  314.     possible_points.push_back(p);
  315.     solution(array_rec,possible_points);
  316.     printf("%d\n",solutions);
  317.     return 0;
  318. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!