How do I find the intersection of rectangles?

[emron]

Hello everybody,
My have a homework and it is very hard for me.
My question: How do I find the intersection of rectangles?

My homework shortly;

You're looking far away from a city and the sun goes down behind the city. Therefore, it is impossible to select buildings individually. It needs to be selected as plural. Find the surroundings of buildings requested from me (as in the picture).

Position = The lower left corner of the rectangles.
The program runs until -1 is entered in the program.
Note: Rectangles (buildings) do not need to be in any order.
In addition, the order of the buildings can be mixed.

Picture:(Turkish only table English)
https://imgur.com/a/aGHA7wU
https://imgur.com/a/vpYN4Tv

My code:

#include <stdio.h>

main()
{	
	int a=0,b=0,c=0;
	int i,j,x=0;
	int dizi[299];
	int k=0;
	int cevre[100];
	int sonuc;
	int min;
	
	
	for(i=0;i<=100;i++)
	{
		scanf("%d",&a);
		if(a==-1)
		{
		//printf("%d",cevre[3]);
		break;
		}
		else
		{
		scanf("%d",&b);
		scanf("%d",&c);
		}
		dizi[x]={a};
		dizi[x+1]={b};
		dizi[x+2]={c};
		cevre[k]=(2*dizi[x])+(2*dizi[x+1]);				
		x+=3;
		k++;
		
	
	}
	

	
/*	printf("%d%d%d",dizi[0],dizi[1],dizi[2]);
	printf("%d%d%d",dizi[3],dizi[4],dizi[5]);
*/
	
	
	return 0;
}

[ne555]

things to notice:
- the rectangles are axis aligned
- their bottom is at 0
- you care about the perimeter, not about the area

you can represent each rectangle with three parameter: the x of the left and right segments and the y of the top
to see if rectangle A intersects with rectangle B you need to check
- A_left or A_right crosses B_top
- or B_left or B_right crosses A_top

def intersect(A, B):
   return crosses(A, B) or crosses(B, A)

def crosses(A, B):
   (between(B.left, A.left, B.right) or between(B.left, A.right, B.right)) and A.top > B.top

def between(a, b, c):
   return a<b and b<c

take care when there is edge superposition

[lastchance]

#include <iostream>
#include <sstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

//==========================================================

struct Rectangle
{
   int L, R, H;                                                 // left, right, height
};

//==========================================================

istream & operator >> ( istream &str, Rectangle &rect )         // Stream extraction for a rectangle
{
   int W;
   str >> W;

   if ( W < 0 )                                                 // Put the stream in a failed state
   {
      str.setstate( ios::failbit );
   }
   else
   {
      str >> rect.H >> rect.L;
      rect.R = rect.L + W;
   }

   return str;
}

//==========================================================

vector<pair<int,int>> skyline( vector<Rectangle> buildings )    // Returns the skyline as (x,y) pairs
{
   vector<pair<int,int>> perimeter;
   if ( buildings.size() == 0 ) return perimeter;               // Trivial case

   // Put buildings in order of height, tallest first
   sort( buildings.begin(), buildings.end(), []( Rectangle r, Rectangle s ){ return r.H > s.H;} );

   vector<Rectangle> visible;                         // To hold non-overlapping visible sub-blocks

   // Tallest building (always seen)
   visible.push_back( buildings[0] );

   // Deal with each of the remaining buildings, collecting what can be seen into visible()
   for ( int i = 1; i < buildings.size(); i++ )
   {
      vector<Rectangle> oneBuilding, temp = { buildings[i] };
      // Add any visible parts of this rectangle to visible()
      for ( int j = 0; j < visible.size(); j++ )
      {
         oneBuilding = temp;
         temp.clear();
         for ( Rectangle rect : oneBuilding )
         {
            if ( rect.R < visible[j].L || rect.L > visible[j].R )    // Completely visible
            {
               temp.push_back( rect );
            }
            else if ( rect.L < visible[j].L && rect.R > visible[j].R )
            {
               temp.push_back( { rect.L, visible[j].L, rect.H } );   // Two ends visible
               temp.push_back( { visible[j].R, rect.R, rect.H } );   //
            }
            else if ( rect.L < visible[j].L )
            {
               temp.push_back( { rect.L, visible[j].L, rect.H } );   // Left end visible
            }
            else if ( rect.R > visible[j].R )
            {
               temp.push_back( { visible[j].R, rect.R, rect.H } );   // Right end visible
            }
         }
      }
      if ( !temp.empty() ) visible.insert( visible.end(), temp.begin(), temp.end() );
   }


   // Sort visible() by position
   sort( visible.begin(), visible.end(), []( Rectangle r, Rectangle s ){ return r.L < s.L; } );


   // Convert visible() to a skyline
   perimeter.push_back( { visible[0].L, 0 } );                       // Start point
   perimeter.push_back( { visible[0].L, visible[0].H } );            // Top-left of 0-th block
   for ( int i = 0; i < visible.size() - 1; i++ )
   {
      perimeter.push_back( { visible[i].R, visible[i].H } );         // Right of i-th horizontal
      if ( visible[i+1].L > visible[i].R )                           // If gap in skyline ...
      {
         perimeter.push_back( { visible[i].R, 0 } );                 //    Go down to floor
         perimeter.push_back( { visible[i+1].L, 0 } );               //    Go to start of (i+1)-th block
      }
      perimeter.push_back( { visible[i+1].L, visible[i+1].H } );     // Top-left of (i+1)-th block
   }
   int i = visible.size() - 1;
   perimeter.push_back( { visible[i].R, visible[i].H } );            // Last horizontal
   perimeter.push_back( { visible[i].R, 0            } );            // Final point at floor

   return perimeter;
}

//==========================================================

int main()
{
   stringstream in( " 3 11  3 "
                    "10  7  1 "
                    " 5  9  9 "
                    "12  4  8 "
                    " 3  9 17 "
                    " 2  3 19 "
                    " -1      " );

   vector<Rectangle> buildings;
   Rectangle rect;
   while( in >> rect ) buildings.push_back( rect );

   vector<pair<int,int>> perimeter = skyline( buildings );
   cout << "Skyline is (x,y):\n";
   for ( auto e : perimeter ) cout << e.first << '\t' << e.second << '\n';
}

//========================================================== 

Skyline is (x,y):
1	0
1	7
3	7
3	11
6	11
6	7
9	7
9	9
14	9
14	4
17	4
17	9
20	9
20	3
21	3
21	0