Please help in this question ::

https://www.hackerearth.com/challenges/college/iste-prodyogiki-long-coding-challenge-2019/algorithm/68915f0bd175451f95f5c606858340d0/

Find convex hull of these points and you will get points as output of convex hull functionâ€¦

Those are the points(gaurds) who will be on perimeter.

But here imo is a twistâ€¦ suppose n soldiers are on perimeter of walls(colinear) the hull will only return two (will skip middle n-2 maybe)

So also add those soldiers in O(n^3) (check every point if itâ€™s between any pair of points from output of hull)

How to find convex hull ?

Googleâ€¦ There are plenty of algos availableâ€¦

I havenâ€™t tried submitting itâ€¦

I may have misunderstood

3 Likes

Also note that above solution is lot more optimized than requiredâ€¦ Expected solution maybe be very easy as points coordinates are only from 0 to 5â€¦ And n<32

Thanks a lot bro

1 Like