CONTAIN, CONVAIR video solution (JUNE20)

CONTAINS :- solution
CONVAIR :- solution

1 Like

convair solution added

I implemented a pretty similar approach to problem CONTAIN, can you tell me why did it give wrong answer in small test case and TLE in bigger cases
Link to my code: https://www.codechef.com/viewsolution/34403259

:+1:

1 Like

You have used Jarvis algorithm which runs in O(n^2). And for finding all the convex layers, the upper bound of time complexity will be O(n^3). That’s why you are getting TLE. Use graham’s scan.
I am not able to figure out the reason for wrong answer but I think I will be some implementation error as your algo is correct.

Thanks for seeing my solution and telling me the mistake. Actually I have no knowledge of Convex hull algorithms :confused: Can you tell me where can I learn to be good at geometry?

Checkout the geometry section of cp-algorithms

Thanks very much