 RNDCHULL - Editorial

To solve this problem, we need to remember the Shoelace formula - Wikipedia for the area of a polygon.

Shoelace formula: If (x_1,y_1),(x_2,y_2),\dots, (x_n, y_n) are the vertices of a convex polygon in counter-clockwise order, then its area is
S = \frac{x_1y_2 - x_2y_1 + x_2y_3 - x_3y_2 + \ldots + x_ny_1 - x_1y_n}{2} .

An alternative way to write the previous formula is (u\wedge v denotes the vector-product between two points, namely u\wedge v:= u_xv_y-u_yv_x)
2S = \sum_{\overrightarrow{uv}\text{ is an edge}} u\wedge v .
Thus, we can compute the contribution to the answer independently for each edge \overrightarrow{uv} and then sum all the contributions.

So, the problem reduces to the following.

Subproblem: Fix an edge p:=(x_{n-1}, y_{n-1}), q=(x_n, y_n) (note that because of orientation edges \overrightarrow{pq} and \overrightarrow{qp} are considered different).
Compute the number of permutations \sigma so that \overrightarrow{pq} belongs to the convex hull of (x_1, y_{\sigma_1}), (x_2, y_{\sigma_2}), \dots, (x_n, y_{\sigma_n}).

Solution of the subproblem:
The edge \overrightarrow{pq} belongs to the convex hull iff \sigma_{n-1}=n-1,\sigma_n=n and the point (x_i, y_{\sigma_i}) is on the left of the oriented line \overrightarrow{pq} for all 1\le i\le n-2.

Assume that p_x>q_x and p_y>q_y (the other cases are equivalent). For each 1\le i\le n-2, the condition (x_i, y) is on the left of \overrightarrow{pq} is equivalent to y < \tilde{y} for some value of \tilde y\in\mathbb R. Therefore, since the array y is sorted, the condition (x_i, y_{\sigma_i}) is on the left of \overrightarrow{pq} is equivalent to \sigma_i\le a_i for some 0\le a_i\le n-2 which can be easily computed. Since the array x is sorted, the values of a_i are increasing.
It remains to count the permutations of \{1, 2,\dots, n-2\} such that \sigma_i\le a_i. It is not hard to show that the number of such permutations is
a_1(a_2-1)(a_3-2)\cdots(a_{n-2}-(n-3)).

So, what is the overall complexity of this solution? There are O(n^4) possible choices for the edge \overrightarrow{uv} (we have to choose the two x coordinates and the two y coordinates); the subproblem can be solved in a naïve way in O(n^2). So we have described an algorithm with complexity O(n^6) which can get accepted if implemented properly. Let us remark that it is also possible to solve the subproblem in O(n) and get an overall complexity of O(n^5), and it is also possible to solve the problem in O(n^4) but this was not necessary to get accepted.

Achtung: Be careful with collinear points.

2 Likes

Wow just beautiful. This was a very nice quality problem! I liked it a lot.