2. Rectangular Area #

Created Tuesday 30 June 2020

CodingNinjas has given you N rectangles, which are centered in the center of the Cartesian coordinate system and their sides are parallel to the coordinate axes. Fach rectangle is uniquely identified with its width (along the x axis) and height (along the y-axis). Navdeep has coloured each rectangle in a certain colour and now wants to know the area of the coloured part of the paper. Please refer to the image below for more details. The given image for the test case

Sample input 1: 3 8 2 (represented by black coloured rectangle) 4 4 (represented by blue coloured rectangle) 2 6 (represented by yellow coloured rectangle) Sample output 1: 28 In other words, he wants to know the number of unit squares that belong to at least one rectangle.

Solution: We’ll not use Parikh’s solution as that’s too granular. And too slow if big numbers are involved. Approach:

1. Step 1 - Take the input coordinates.
2. See only the 1st quadrant, like steps.
3. For each point on the x-axis, till the point on the left, the height is the same as the current point.
4. Area for a point p = (p.x-p~left~.x)*p.y
5. For the left most point, we need a point on the left. We’ll add it to the input.

Code:

1. Make a pair<int, int> array of size n+1. 1 for the left most
2. Take the inputs, record the maximum height, the left most point is (0, hmax).
3. Sort the array(by default happens with the first in pair, x coordinate)
4. For each point, traverse for all the point entries with same X:
   1. calculate hmax_local for them.
   2. Set the starting point’s X as hmax_local
   3. Continue to the next point(i.e with the next value of X)
   4. Keep a counter of the number of distinct points = neff
5. Traverse neff from right to left. area+=(p.x-p~left~.x)*p.y
6. We don’t need to multiply 4. As we never subtracted the input by 4. No floats required, easy.

rect_area.cpp