Editorial : Star Map

This editorial follows model_sol.cpp: sort stars by $x$, sweep left to right, and greedily form harmonious triangles from alternating extrema on an upper and lower chain in $y$.

Distinct $x$ and $y$ let us order points by $x$. Three points that appear consecutively in this order with the middle point forming a local maximum (upper chain) or local minimum (lower chain) in $y$ lie on three sides of some axis-aligned rectangle, so the triangle is harmonious.

After sorting by x:

• up stack (upper chain): before pushing the current point p, while the last two entries prev, top satisfy top.y > prev.y and top.y > p.y, emit triangle (prev.id, top.id, p.id) and pop top. Push p.

• down stack (lower chain): symmetrically while top.y < prev.y and top.y < p.y, emit a triangle and pop.

The vector tri collects all triangles; print its size and triples. The construction aims for maximal count under the “disjoint interiors” rule; the stack peeling matches the reference solution’s greedy choice.

Sorting dominates: $O(n \log n)$ per test case; the sweep is linear.