Question

Two boxes overlap if their interiors have at least one point in common. Give an O(n log n)-time algorithm that decides if there is a pair of boxes in S that overlap and produces one such pair if it exists

Answer 1

// Program is written in C++ programming language

// The program checks if two boxes overlap and prints both boxes

// Comments are used for explanatory purpose

// Program starts here

#include<bits/stdc++.h>

#include <graphics.h>

#include <conio.h>

// Define x and y axis

struct axis { int x, y; };

bool checkRect(Axis l1, Axis r1, Axis l2, Axis r2)

{ // l1, l2, r1 and r2 represent the left and right coordinates of both rectangles

// Check one rectangle is on left side of other

if (l1.x > r2.x || l2.x > r1.x) {

return false; }

// Check if one rectangle is above other

if (l1.y < r2.y || l2.y < r1.y) {

return false; }

return true;

}

// Main Method begins here

int main()

{

// Declare integer variables to enter rectangle coordinates

// For rectangle 1

int left1, left2, right1, right2;

cout<<"Enter First rectangle coordinates: "<<"\\";

cout<<"Top Left: "<<"\\";

cin>>left1;

cout<<"Bottom Left: "<<"\\";

cin>>left2;

cout<<"Top Right: "<<"\\";

cin>>right1;

cout<<"Bottom Right: "<<"\\";

cin>>right2;

// For rectangle 2

int left3, left4, right3, right4;

cout<<"Enter Second rectangle coordinates: "<<"\\";

cout<<"Top Left: "<<"\\";

cin>>left3;

cout<<"Bottom Left: "<<"\\";

cin>>left4;

cout<<"Top Right: "<<"\\";

cin>>right3;

cout<<"Bottom Right: "<<"\\";

cin>>right4;

Axis l1 = {left1, left2}, r1 = {right1, right2};

Axis l2 = {left3, left4}, r2 = {right3, right4};

if (checkRect(l1, r1, l2, r2)) {

cout<<"The Rectangles Overlap"; }

else {

cout<<"Rectangles Don't Overlap";}

// Print Rectangle 1

rectangle (left1, right1, left2, right2);

// Print Rectangle 2

rectangle (left3, right3, left4, right4);

return 0;

}