কনভেক্স হাল(Convex Hull)

If you don't know what Convex Hull is,read the following articles sequentially.Hope,you'll get vast knowledge.Since there are a lot of tutorials on Convex Hull,we'll rather discuss here some related problems & their solutions.

Tutorials on Convex Hull & it's prerequisites:

1.Orientation of 3 ordered points(prerequisite)
2.How to check if two given line segments intersect?(prerequisite)
3.Implementation of Graham Scan Algorithm for Convex Hull(Implementation)

Sample source Code:

Related Problems & Solutions:

1. LightOj 1203 - Guarding Bananas

          Solution Idea: Straightforward

          i) Make Convex Hull of the given points.

          ii) Find angle for each point with respect to it's adjacent line segment.

          iii) Answer the minimum of them(angles).

          iv) If a,b,c are line segments & ∆abc is a triangle,the angle between a & c is acos((a*a+c*c-b*b)/2*a*c)) in radian.

          v) degree=radian*(180/𝞹).

Solution:

2. LightOj 1239 - Convex Fence
          Solution Idea: Straightforward
          i) Make Convex Hull of the given points.
          ii) Find it's perimeter.
          But this is not the actual answer,we've to add 2*𝞹*d to it.why?Because the problem indicates that the minimum distance of any tree to fence at least d units.
          if we think of n=1,we can assume it as circle of radius d.So,the answer will be mere 2*𝞹*d(perimeter of the circle).
          if we think of n=2, we can imagine the following picture(collected)

if we think of n>2,we can imagine the following pictures(collected)

From the above pictures,it is clear that joining several same circles make 360°.So the solution is simple,add 2*𝞹*d to the perimeter of the Convex Hull(n>2).

Solution:

3. SPOJ BSHEEP - Build the Fence
          Solution Idea: Straightforward
          i) Make Convex Hull of the given points.
          ii) Find it's perimeter & print.
          iii) Print the indexes by which the Convex Hull is formed.

Solution:
4.