Thursday, August 21, 2014

Chef and the Cake I


Problem Link : http://www.codechef.com/problems/CAKE1AM/

Idea : We have to calculate the area that covers by two rectangle . Given the co-ordinate in 2D space . Our answer is the summation of the area of the two rectangle minus the area that they intersect , that also a rectangle . If we analyze some case , we can easily understand that their intersection rectangle's lower left corner is the maximum x co-ordinate and the maximum y co-ordinate of all the lower left points as wll as its upper right corner is the minimum x co-ordinate and the minimum y co-ordinate of all the upper right points . Tf the two point makes a rectangle , that means the two rectangle intersects . The two point makes a rectangle if the x and y co-ordinate of second point is larger than first .
Take input for co-ordinate of 4 points .

Add result the area made by the two rectangle . As shown below -

result+=(x2-x1)*(y2-y1)+(x4-x3)*(y4-y3)

If the rectangle intersects , subtract the area made by intersection rectangle from result . Show output .

My solution

No comments:

Post a Comment