Author: | Roman Bilyi |
Prepared by: | Maksym Shcherba |
Solved by: | |
First to solve: | N/A |
If the convex hull of all points is not triangle, the answer is 0. Let A, B, C be the points on convex hull in clockwise direction. Let’s check if for the 3 points X, Y, Z all subset convex hulls are triangles.
Firstly, let’s add points B and C to the subset, they should be on the convex hull so wlog let the convex hull be X, B, C. If X, Y, Z is good then X, B, C should be good as well. Let’s find all possible points X such that triplet X, B, C is good.
Let’s sort all points by angle cw around point B starting with point A, sort all points by angle ccw around point C starting with point A. Triplet X, B, C is good iff the prefixes of both orders up to point X are the same.
Proof. Necessity: If some point D appears only in one prefix (let’s say it appears in point B order), the convex hull of X, B, C, D will be B, D, X, C. If two points E, F have different order, the convex hull of X, B, C, E, F will be B, E, F, C.
Sufficiency: All other points are inside triangle XBC so they are irrelevant. If we add some subset of common prefix, the convex hull will be B, C and the point on the common prefix closest to the chain start. ◻
Let’s call the common prefix of those orders A-chain:
A-chain.
If we add points A, B to the subset X, Y, Z, it’s impossible that the same point X remains on the convex hull (X, A, B).
Proof. It means that points Y and Z should be inside triangle XBC and triangle XAB simoultaneously which is impossible. ◻
That means that we should have X on A-chain, Y on B-chain, Z on C-chain.
Triplet X, Y, Z is good iff:
The order of all points sorted by angle ccw around point Y starting from YA matches the A-chain up to point X;
The order of all points sorted by angle cw around point Z starting from ZA matches the A-chain up to point X;
The same for points B-chain and C-chain.
Proof. Necessity: If the order around point Y doesn’t match A-chain, we can add point C to the subset, forget about all points outside of triangle AYC and find the same counter example as in Lemma J.1.
Sufficiency:
Since point Y is on B-chain and point Z is on C-chain there could be no points in red areas.
Since the sets of points on the prefixes sorted by angle from point Y and point Z are the same, there could be no points in blue areas.
Points in green area are only points on A-chain and those are in correct order such that it’s impossible to add some subset of them to get non-triangle hull.
Areas accounted.
If we do the same for B-chain and C-chain, we will cover all are outside of triangle XYZ and only the points on chains are the ones outside. So the convex hull of each subset will be a triangle containing exactly one point on each chain. The point on each chain will be the one that is the closest to the chain start. ◻
To calculate the answer we can iterate over all pairs of points (Y, Z), and find the number of possible points X using binary search or 2 pointers.
To summarize we need:
Compute convex hull, answer is 0 if it’s not triangle;
Find chains by sorting all points around A, B and C.
For each point, sort all other points around it and compute common prefixes with chains.
Iterate over Y, Z and find the number of valid points X.
Complexity: O(n^2 \log n).
Bonus. The problem looks doable for n \le 10^5. To compute the answer we can iterate over point Z and maintain segment tree for each Y number of valid X. Geometry part is to check the order is the same look possible using intersection of some half-planes. So is it possible?