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
$\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$
  • $\begingroup$ how to find that overlapping area? $\endgroup$ – user3001932 Jan 19 '14 at 17:25
  • $\begingroup$ could you please provide me a formula in terms of the given points? $\endgroup$ – user3001932 Jan 19 '14 at 17:25
  • $\begingroup$ @user3001932 Read the first hint. $\endgroup$ – Calvin Lin Jan 19 '14 at 17:29
  • $\begingroup$ I am not able to deduce a formula for it $\endgroup$ – user3001932 Jan 19 '14 at 17:36

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.