Problem Setter - Rahul Gupta
Quick Explanation-
Question is eqvt to finding the sum over all the points of subset of remaining points that can form a polygon to contain this point.
For each point assuming it as centre and sort all the points clockwise.
Now For each rest of point find the no. of polygons not containing this point.
Explanation
“Chef defined strength of a tree of the planet as the number of distinct subsets of remaining trees whose convex hull can enclose the tree completely and strictly inside it.”
This statement also means a subset of remaining points from which if we create a polygon(of any shape) using all the points then there exist a polygon that can enclose that point.
So problem changes to find the sum over all points the no. of distinct subsets of point that can cover this point.
Now as N\le1000, so it indicates a solution of order of N^{2} or N^{2}logN. Also we will be calculating for every point no. of distinct subsets of points that can’t enclose this point in any way and let this value be X. The remaining points are N-1, so answer for this point will be = (N-1)C3 + (N-1)C4 … +(N-1)C(N-1) - X. You can calculate first part as precomputation (its equal to 2^{N-1} -(NC0 + NC1 + NC2)) as it is same for every point.
Now for every point we will do following.
Assume it as origin and shift other points accordingly. Then we will sort remaining point clockwise. Now remember no three points where collinear. Now for every point, we will take the remaining points one by one and we will create a polygon taking this point and we will take the rest of the points from same half plane. Since all the points are from same half plane, so this polygon surely cant cover the point for which we are calculating subsets. Also doing this for every point will cover all the subsets of point that cant cover this point.
Rest is you can use a two pointer kind of approach to do the processing for every single point. Like first sorting rest of the points clockwise after assuming one as centre, and then concatenate rest of the points again with them and now doing a two pointer kind of approach.
Time Complexity- O(N^{2})