PROBLEM LINK:DIFFICULTY:MEDIUM PROBLEM:Let's consider a 2D plane, where we plug pegs at the points mentioned. We enclose all the pegs with a elastic band and then release it to take its shape. The closed structure formed by elastic band is similar to that of convex hull. Find the perimeter of the convex hull for the points. EXPLANATION:Let points[0..n1] be the input array. 1) Find the bottommost point by comparing y coordinate of all points. If there are two points with same y value, then the point with smaller x coordinate value is considered. Let the bottommost point be P0. Put P0 at first position in output hull. 2) Consider the remaining n1 points and sort them by polor angle in counterclockwise order around points[0]. If polor angle of two points is same, then put the nearest point first. 3 After sorting, check if two or more points have same angle. If two more points have same angle, then remove all same angle points except the point farthest from P0. Let the size of new array be m. 4) Create an empty stack ‘S’ and push points[0], points[1] and points[2] to S. 5) Process remainning m3 points one by one.Do following for every point 'points[i]'. TESTER'S SOLUTION
This question is marked "community wiki".
asked 03 Apr '16, 16:05
