Please advise which case I am not covering

Question

Given 2 rectangles parallel to coordinate axes, find the area covered by them.

Input Format: First line of input contains T - number of test cases. Its followed by 2T lines. First line of each test case contains 4 integers - xbl, ybl, xtr, ytr - the bottom-left and top-right coordinates of rectangle-1. The second line of each test case contains 4 integers - xbl, ybl, xtr, ytr - the bottom-left and top-right coordinates of rectangle-2.

Constraints

1 <= T <= 10000
-10⁶ < x,y <= 10⁶
(xbl, ybl) < (xtr, ytr)

Output Format: For each test case, print the area covered by the 2 rectangles, separated by newline.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

unsigned int recarea(int x1,int y1,int x2,int y2){
    int area=0;
    area=(x2-x1)*(y2-y1);
    return abs(area);
}

unsigned int overarea(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    int top=fmin(y2,y4);
    int bottom=fmax(y1,y3);
    int left=fmax(x1,x3);
    int right=fmin(x2,x4);
    int overlaparea=0;
    if(bottom<top && left<right){
        overlaparea=recarea(left,bottom,right,top);
    }
    return abs(overlaparea);
}

int main() {
    int testcases=0;
    scanf("%d",&testcases);
    for(int i=0;i<testcases;i++){
        int x1,x2,y1,y2,x3,x4,y3,y4;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
        int area=recarea(x1,y1,x2,y2)+recarea(x3,y3,x4,y4)- 
         overarea(x1,y1,x2,y2,x3,y3,x4,y4);
        printf("%d\n",area);
    }   
    return 0;
}

The variables x1, y1 are bottom left coordinates and x2, y2 are top right coordinates for Rectangle 1. The variables x3, y3 are bottom left coordinates and x4, y4 are top right coordinates for Rectangle 2.

Do you have a test case that is failing? Have you run that case in the debugger to see why? — Retired Ninja
Hi Retired Ninja. The test case is hidden. Every thing seems to be perfect for me. — user218324
If x1 = -99999, y1 = -99999, x2 = 99999, y2 = 99999 then your code will overflow the size of a 32-bit int. If that's the case then you should use an int64_t. — Yakov Galka

chux - Reinstate Monica chux - Reinstate Monica · Accepted Answer · 2019-05-25T21:10:53

Please advise which case I am not covering

Use wider math

area=(x2-x1)*(y2-y1); is prone to int overflow given -10⁶ < x,y <= 10⁶.

The max area is about 4*10¹², outside the range of most int implementions (32 or 16 bit).

long long covers at least the range -(2⁶³ + 1) ... +(2⁶³ + 1)

long long recarea(int x1, int y1, int x2, int y2) {
    long long area = (0LL + x2 - x1)*(0LL + y2 - y1);
    return llabs(area);
}

   long long area = recarea(...
   printf("%lld\n",area);

Adjust overarea() too.

Other

Other functional problems may exist. Example: int may be as small as 16-bit. Consider using long instead to handle -10⁶ < x,y <= 10⁶.

Aside

Code is using floating point functions with fmin(), fmax(). I'd used a integer only approach rather than incur various problems switching between FP and integer. Looks OK here given the small range, but not for larger values.

Please advise which case I am not covering

1 Answers