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
Labels:
Geometry
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment