10
\$\begingroup\$

I was very intrigued with the manner to solve this problem. The program needs to know if 2 rectangles fit in another one, considering the lines of the 2 rectangles are always parallel to the other one's.

I know I could just put everything in a single if, but is that more readable? I want to know a good approach for this situation, using only conditions.

NOTE: x and y represent the first rectangle's width and height (the one that will fit the other 2) and l1, h1, l2, and h2 represent the other 2 rectangles' width and height.

#include <stdio.h>                                                                                  

int main(void)                                                                                      
{                                                                                                                                         
    int x, y, l1, h1, l2, h2;                                                                       

    scanf("%d %d %d %d %d %d", &x, &y, &l1, &h1, &l2, &h2);                                         

    if ((l1 + l2 <= x && h1 <= y && h2 <= y) || 
    (h1 + h2 <= x && l1 <= y && l2 <= y))               
    {                                                                                               
        puts("They fit.");                                                                                                                                                           
    }                                                                                                                       
    else if ((l1 <= x && h2 <= x && h1 + l2 <= y) || 
    (h1 <= x && l2 <= x && l1 + h2 <= y))          
    {                                                                                               
        puts("They fit.");                                                                                                                                                             
    }                                                                                                                        
    else if ((l1 <= y && h2 <= y && h1 + l2 <= x) || 
    (h1 <= y && l2 <= y && l1 + h2 <= x))          
    {                                                                                               
        puts("They fit.");                                                                                                                                                             
    }                                                                                                                       
    else if ((l1 + l2 <= y && h1 <= x && h2 <= x) || 
    (h1 + h2 <= y && l1 <= x && l2 <= x))          
    {                                                                                               
        puts("They fit.");                                                                                                                                                          
    }                                                                                                                                                               
    else                                                                                            
    {                                                                                               
        puts("They don't fit.");                                                                                                                                                           
    }   
    return 0;
}  
\$\endgroup\$
  • \$\begingroup\$ Problem would have been more interesting without the restriction "considering the lines of the 2 rectangles are always parallel to the other one's". \$\endgroup\$ – chux Jun 27 '16 at 19:52
  • 2
    \$\begingroup\$ Are you concerned about int overflow like in l1 + l2 <= x? \$\endgroup\$ – chux Jun 27 '16 at 19:53
11
\$\begingroup\$

Any two rectangles can fit into a third rectangle (without overlapping with each other) only under 2 cases:

As mentioned in the question, consider:

  • x,y -> length and height of first rectangle into which below two rectangles must fit.
  • l1,h1 -> length/width and height of second rectangle.
  • l2,h2 -> length and height of third rectangle.

Note: You could use structures or 2-dimensional arrays for better readability.


Case 1:

  • When x is greater than or equal to l1+l2

  • Here the height y must be greater than or equal to maximum of h1 and h2 for the rectangles to fit in, else it doesn't fit in.

Case 1

Note: x >= l1+12 can be written as ((x >= l1) && (x-l1 >= l2)). This is to avoid the overflow while adding integers.


Case 2:

  • When y is greater than or equal to h1+h2

  • Here the length x must be greater than or equal to maximum of l1 and l2 for the rectangles to fit in, else it doesn't fit in.

Case 2

Note: similarly, even here y >= h1+h2 can be written as (y >= h1) && (y-h1 >= h2). This is to avoid the overflow while adding integers.


Now, keeping the above 2 cases in mind, a simple function can be constructed this way:

int fit( int x, int y, int l1, int h1, int l2, int h2)
{
    //return 1 for fit and 0 if does not fit

    //case 1 or case 2
    if( ( ((x >= l1) && (x-l1 >= l2)) && y >= max(h1,h2)) || 
        ( ((y >= h1) && (y-h1 >= h2)) && x >= max(l1,l2)) )
    {
            return 1;
    }

    return 0;
}

Note: here max() is a function which returns the larger value among the two sent arguments.

int max(int a, int b)
{
    if(a>b)
    {
        return a;
    }
    return b;
}

Now, the 2 rectangles can be sent in 4 different ways to check if they can fit in the rectangle of dimensions x and y:

//sending as entered by the user
fit( x, y, l1, h1, l2, h2)

//interchanging length and height of anyone rectangle
fit( x, y, h1, l1, l2, h2)

//interchanging length and height of other rectangle
fit( x, y, l1, h1, h2, l2)

//interchanging lengths and heights of both rectangles
fit( x, y, h1, l1, h2, l2)

  • Now, you can easily know whether the rectangles fit or does not fit by checking for the return value of fit() function.
  • If return value of anyone of the above four function calls is 1 then the rectangles fit in!
  • You could use the main() function as:

    int main(void)
    {
        int x, y, l1, h1, l2, h2;
    
        scanf("%d %d %d %d %d %d", &x, &y, &l1, &h1, &l2, &h2);
    
        //tests for fit
        if(fit( x, y, l1, h1, l2, h2) || 
           fit( x, y, h1, l1, l2, h2) || 
           fit( x, y, l1, h1, h2, l2) || 
           fit( x, y, h1, l1, h2, l2))
        {
            printf("fits");
        }
        else
        {
            printf("doesn't fit");
        }
    
    }
    
  • The above if block functions similarly as an else-if ladder because, || stops evaluation on the first true (i.e, function returns 1).

  • So, if any of the function returns a 1, then then "fits" gets printed out and program terminates
  • In case, if none of the function calls return 1 the "doesn't fit" gets printed out and program terminates

Altogether your code would be:

#include <stdio.h>

int max(int a, int b)
{
    if(a>b)
    {
        return a;
    }
    return b;
}

int fit( int x, int y, int l1, int h1, int l2, int h2)
{
    //return 1 for fit and 0 if does not fit

    //case 1 or case 2
    if( ( ((x >= l1) && (x-l1 >= l2)) && y >= max(h1,h2)) || 
        ( ((y >= h1) && (y-h1 >= h2)) && x >= max(l1,l2)) )
    {
            return 1;
    }

    return 0;
}



int main(void)
{
    int x, y, l1, h1, l2, h2;

    scanf("%d %d %d %d %d %d", &x, &y, &l1, &h1, &l2, &h2);

    //tests for fit
    if( fit( x, y, l1, h1, l2, h2) || 
        fit( x, y, h1, l1, l2, h2) || 
        fit( x, y, l1, h1, h2, l2) || 
        fit( x, y, h1, l1, h2, l2))
    {
        printf("fits");
    }
    else
    {
        printf("doesn't fit");
    }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ By using if( (x >= l1) && (x - l1 >= l2 ... instead of if( (x >= l1+l2 ... (same for y), no chance of int overflow. \$\endgroup\$ – chux Jun 27 '16 at 20:40
  • 1
    \$\begingroup\$ @chux thanks for the input... i was not mindful of the int overflow \$\endgroup\$ – Cherubim Jun 27 '16 at 21:33
  • 1
    \$\begingroup\$ @CherubimAnand I like how responsive you are to comments haha. For a few more recommendations on your answer, come see me in the 2nd Monitor \$\endgroup\$ – syb0rg Jun 28 '16 at 13:27
4
\$\begingroup\$

Variable Names
I would use a struct to represent each rectangle, variables within the struct would be height and width. The struct could be named rect with instances of rect1, rect2 and rect3.

If you don't use a struct, use better variable names such as rect1x, rect1y.

Prompt For Input
You need to ask the user a question before you scan the input.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer! Well, I used those names because I had to use them. Was required in the problem specification. Also, I had to leave the input as it was, with no text. Good advice with the structs, though! \$\endgroup\$ – Lúcio Cardoso Jun 26 '16 at 17:02
2
\$\begingroup\$

You are making two assumptions:

  1. All rectangles share the same origin.
  2. The inner rectangles don't overlap.

In general, the first assumption doesn't seem very reasonable, as a 2D rectangle can be anywhere in the XY plane, not necessarily at the origin.

The second assumption might be what you want, but it is easy to check for overlap of the two inner rects without too much extra work.

Here's an alternate solution:

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

//
// Origin at the top.
//
// (x:0, y:0)
//     +---------+
//     |         |
//     |         |
//     |         |
//     +---------+
//         (width:M, height:N)
//
typedef struct {
    int x;
    int y;
    int width;
    int height;
} Rectangle;

bool contains(const Rectangle * rect, const Rectangle * test)
{
    if (test->x < rect->x || test->y < rect->y) {
        return false;
    }
    if (test->x > rect->x + rect->width ||
        test->y > rect->y + rect->height) {
        return false;
    }
    if (test->x + test->width  > rect->x + rect->width ||
        test->y + test->height > rect->y + rect->height) {
        return false;
    }
    return true;
}

bool pointInside(const Rectangle * rect, int x, int y)
{
    if (x < rect->x || x > rect->x + rect->width) {
        return false;
    }
    if (y < rect->y || y > rect->y + rect->width) {
        return false;
    }
    return true;
}

bool overlap(const Rectangle * a, const Rectangle * b)
{
    if (pointInside(a, b->x, b->y) ||
        pointInside(a, b->x + b->width, b->y + b->height)) {
        return true;
    }
    if (pointInside(b, a->x, a->y) ||
        pointInside(b, a->x + a->width, a->y + a->height)) {
        return true;
    }
    return false;
}

void readInput(Rectangle * rect)
{
    if (scanf("%i %i %i %i", &rect->x, &rect->y, &rect->width, &rect->height) != 4) {
        fprintf(stderr, "invalid input!\n");
        exit(EXIT_FAILURE);
    }
}

int main(void)
{
    Rectangle parentRect;
    Rectangle rect0;
    Rectangle rect1;
    bool cleanFit = true;

    printf("\ncoords of parent rectangle? (x y w h)\n");
    readInput(&parentRect);

    printf("\ncoords of first rectangle? (x y w h)\n");
    readInput(&rect0);

    printf("\ncoords of second rectangle? (x y w h)\n");
    readInput(&rect1);

    printf("\n");

    // First check if both are contained inside the parent rectangle:
    if (!contains(&parentRect, &rect0)) {
        cleanFit = false;
        printf("first rectangle not fully contained inside the parent\n");
    }
    if (!contains(&parentRect, &rect1)) {
        cleanFit = false;
        printf("second rectangle not fully contained inside the parent\n");
    }

    // Both contained inside the parent, now make sure
    // rect0 and rect1 do not overlap with each other.
    if (overlap(&rect0, &rect1)) {
        cleanFit = false;
        printf("first and second child rectangles overlap\n");
    }

    if (cleanFit) {
        printf("rectangles fit without overlap!\n");
    }

    return 0;
}

Things I did differently

Notice that I have used a structure to define a new type, so we can have named rectangles instead of a bunch of loose variables.

I have also added a couple helper functions, since some code is repeated, we should avoid copy-pasting. Creating functions also gives names to common operations: contains, overlap, readInput, etc.

Well named variables are very important. The names you use in your code are quite generic.

Always check if the input operation succeeded! If scanf can't parse enough elements from the input, it will just leave the variables uninitialized, which can result in some pretty nasty bugs. Test the return value to make sure you've got what you expected.

\$\endgroup\$
  • \$\begingroup\$ In the original problem, the positions are not specified, and the two rectangles can be rearranged by moving and/or rotating to fit in the first rectangle. \$\endgroup\$ – Risky Martin Jun 27 '16 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.