Triangle Hull#13017

Triangle Hull (Editorial)

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:

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:

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:

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?