1
$\begingroup$

Given a large rectangle I decided to take two pieces.

For the first piece make a rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake have two pieces. I take the piece inside the rectangle cut. For the second piece, make another rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake again have two pieces. I take the piece inside the rectangle cut (note that this piece may not be rectangular, because of cut may cross an empty space that remains from the first piece, also it can be empty).

Given the cuts determine the amount of cake that I will have. The amount is calculated as the sum of the areas covered by your pieces.

Example : A rectangle is defined by four integers (co-ordinate of the lower-left corner (x1,y1) and upper right corner (x2,y2)).Let here they are : -

Piece 1 : (1,1) and (20,20)

Piece 1 : (11,11) and (30,30)

Here answer will be 641.

$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

Hint: A rectangle, with sides parallel to the axis, is uniquely determined by it's lower left point and the upper right point.

Hint: Apply the principle of inclusion and exclusion. To find the total area, you need to find the sum of the individual areas, and subtract the overlapped area (if any).

In your example, we get $ 641 = 19^2 + 19^2 - 9 ^2 $.

$\endgroup$
4
  • $\begingroup$ how to find that overlapping area? $\endgroup$
    – user3001932
    Jan 19, 2014 at 17:25
  • $\begingroup$ could you please provide me a formula in terms of the given points? $\endgroup$
    – user3001932
    Jan 19, 2014 at 17:25
  • $\begingroup$ @user3001932 Read the first hint. $\endgroup$
    – Calvin Lin
    Jan 19, 2014 at 17:29
  • $\begingroup$ I am not able to deduce a formula for it $\endgroup$
    – user3001932
    Jan 19, 2014 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .