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;
- }Point;
- bool check_intersection(Rectangle *array_rec,vector<Point> &occupied_points,Point toplace,int rec,int orientation);
- bool place_rectangle(Rectangle *array_rec,vector<Point> &occupied_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,int*solutions, long* area,vector<Point> &occupied_points,int rec);
- int main() {
- int solutions=0;
- Rectangle* array_rec=new Rectangle[n_rectangles]; /* array que guarda as medidas de cada rectangulo*/
- vector <Point> occupied_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,&solutions,&area,occupied_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 solution(Rectangle *array_rec,int*solutions, long* area,vector<Point> &occupied_points,int rec){
- int first_placed=0;
- for(int j=0;j<n_rectangles;j++){
- if(array_rec[j].first_placed_vertical){
- first_placed++;
- }
- }
- if(first_placed==n_rectangles){
- return true;
- }
- if(accept_solution(array_rec)){
- for(int i=0;i<n_rectangles;i++){
- array_rec[i].placed=false;
- }
- total_height=0;
- total_width=0;
- occupied_points.clear();
- return true;
- }
- for(int i=0;i<(n_rectangles);i++){
- if(!array_rec[i].placed){
- if(occupied_points.empty()){
- if(!array_rec[i].first_placed_vertical) {
- Point point = {0, 0};
- place_rectangle(array_rec, occupied_points, point, i);
- array_rec[i].placed = true;
- array_rec[i].first_placed_vertical = true;
- solution(array_rec, solutions, area, occupied_points, i + 1);
- }
- }
- else{
- for(int p=0;p<(int)occupied_points.size();p++){
- if(place_rectangle(array_rec,occupied_points,occupied_points[p],i)){
- array_rec[i].placed=true;
- if(solution(array_rec,solutions,area,occupied_points,i+1)){
- *solutions+=1;
- total_height=0;
- total_width=0;
- occupied_points.clear();
- }
- array_rec[i].placed=false;
- }
- }if(array_rec[i].placed==false){
- Point aux;
- for (int x = 0; x<n_rectangles;x++){
- if(array_rec[x].placed){
- if( array_rec[x].ulc[1]==occupied_points[(int)occupied_points.size()-2].y && array_rec[x].ulc[0]==occupied_points[(int)occupied_points.size()-2].x && array_rec[x].brc[1]==occupied_points[(int)occupied_points.size()-1].y && array_rec[x].brc[0]==occupied_points[(int)occupied_points.size()-1].x ){
- array_rec[x].ulc[0]=NULL;
- array_rec[x].ulc[1]=NULL;
- array_rec[x].brc[0]=NULL;
- array_rec[x].brc[1]=NULL;
- array_rec[x].placed=false;
- aux={array_rec[x].blc[0],array_rec[x].blc[1]};
- }
- }
- }
- occupied_points.erase(occupied_points.end()-1);
- occupied_points.erase(occupied_points.end()-2);
- occupied_points.push_back(aux);
- }
- }
- }
- }
- return false;
- }
- bool place_rectangle(Rectangle *array_rec,vector<Point> &occupied_points,Point toplace,int rec){
- 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,occupied_points,toplace,rec,0)) {
- Point ulc = {array_rec[rec].ulc[0], array_rec[rec].ulc[1]};
- Point brc = {array_rec[rec].brc[0], array_rec[rec].brc[1]};
- printf("Point ulc: %d %d Point brc: %d %d \n", ulc.x, ulc.y, brc.x, brc.y);
- occupied_points.push_back(ulc);
- occupied_points.push_back(brc);
- for(int s=0;s<(int)occupied_points.size();s++){
- if(occupied_points[s].x==toplace.x && occupied_points[s].y==toplace.y){
- occupied_points.erase(occupied_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,occupied_points,toplace,rec,1)){
- Point ulc = {array_rec[rec].ulc[0], array_rec[rec].ulc[1]};
- Point brc = {array_rec[rec].brc[0], array_rec[rec].brc[1]};
- printf("Point ulc: %d %d Point brc: %d %d \n", ulc.x, ulc.y, brc.x, brc.y);
- occupied_points.push_back(ulc);
- occupied_points.push_back(brc);
- for(int s=0;s<(int)occupied_points.size();s++){
- if(occupied_points[s].x==toplace.x && occupied_points[s].y==toplace.y){
- occupied_points.erase(occupied_points.begin()+s);
- }
- }
- return true;
- }
- array_rec[rec]=aux_rec;
- return false;
- }
- }
- bool check_intersection(Rectangle *array_rec,vector<Point> &occupied_points,Point toplace,int rec,int orientation){ /* orientation: 0 vertical 1 horizontal*/
- for (int i = 0; i < (int) occupied_points.size(); i++) {
- if(orientation==0) {
- if (toplace.x + array_rec[rec].width < occupied_points[i].x && toplace.y + array_rec[rec].height < occupied_points[i].y) {
- printf("false intercestion\n");
- return false;
- }
- }
- else{
- if (toplace.x + array_rec[rec].height < occupied_points[i].x && toplace.y + array_rec[rec].width < occupied_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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement