## Editorial for COCI '21 Contest 3 #5 Kućice

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

For the first subtask, the number of points within the convex hull of any subset of points is equal to the size of that subset, so the expected value is and .

We can calculate by going over each of the subsets of points, finding the convex hull and checking to see how many points lie in the hull. A naive implementation of this was sufficient to solve the subtask in which .

We can also calculate in a different way - by fixing a point and counting how many subsets there are where the point lies in the hull. It turns out that it's easier to count the complement, i.e. how many subsets there are whose hull doesn't contain the fixed point. Notice that after fixing a point and a subset whose hull doesn't contain it, there is always a line that passes through the point, but which doesn't intersect the hull. If we call the fixed point , we can think of this line as rotating around counterclockwise until it hits a point on the hull (see image above).

For a fixed choice of and it is sufficient to find the number of points which lie on one side of the line . If we call this number (not counting ), then the number of subsets whose hull doesn't contain and for which is the point that is 'first in the counterclockwise direction' is .

Therefore, the solution can be determined in the following way. Fix a point and sort the remaining points circularly around . Iterate over and maintain the number of points on each side of the line . The points in a halfplane form a circular segment, so it is enough to maintain the last point (with respect to the circular order) that is still in the current halfplane, using the method of two pointers. For each point we do one sort in and then calculate the number of subsets not containing in with two pointers. The total complexity is then .

For the circular sort and for maintaining the current halfplane it is helpful to use the function which determines for three given points , and whether they are listed in counterclockwise order:

where if and only if the points , and are listed in counterclockwise order. To sort the points circularly, we can divide them into the ones above and the ones below point , sort these two groups separately, and then merge them. Within a group we use the function as a comparator with arguments being the two points in question and the fixed point .

## Comments