how to use convex-hull concept to solve this problem

Question

I was solving this SPOJ problem which uses concept of convex hull.

Go through the above link to understand the question completely

If this problem is changed a little bit and we are given a point say A(x,y) and asked to find maximum number of fences only around that particular point .

My Approach

(Correct me if i am wrong)

1.Find the maximum number of non-intersecting ,non-touching convex hulls that can be formed from N points(given in the problem)

2.Find the number of hulls for which the the point A lies inside it.

Please help me how to approach this problem ??

P.S. :- I couldn't find any similar problem so that i could validate my approach . If you find any similar problem do attach below.

Thanks.

Answer 1

Your approach works fine. Both your problem and the SPOJ problem can be considered recursively as follows.

Given a set of poles:

1. determine the best possible outer-most fence
2. Solve the problem again with the poles inside that fence

Note that adding another pole to the problem will never lead to a worse result, because you can always just not use it.

So, in step (1), the convex hull of the available poles is always a valid choice, because the set of poles inside it is a superset of the poles remaining after any other choice. For your problem, it will also enclose the point A if any other choice does.