Problem analysis: Counting Zs (stage III, XXXIII OI)

Introduction

The problem provides the coordinates of \(n\) pairwise distinct points on a plane. For an ordered quadruple \((A, B, C, D)\), we say it forms the letter \(Z\) if \(0^\circ < \angle ABC = \angle DCB < 90^\circ\), where \(\angle ABC\) denotes the measure of the angle formed by points \(A, B, C\) calculated counterclockwise. Thus, one can think of the letter \(Z\) as two parallel segments \(AB\) and \(DC\) connected by a "middle" segment \(BC\), adjacent to which are two equal, acute angles. Our task is to count all such quadruples.

\(O(n^3)\) Time Solution

The first step is to decide which object we will iterate over. A natural candidate is the "middle" segment of the letter \(Z\), i.e., the pair \((B, C).\) For a fixed \(BC\), it is the common arm of the angles \(\angle ABC\) and \(\angle DCB\), so the letter \(Z\) is formed simply by "choosing" the endpoints: point \(A\) at \(B\) and point \(D\) at \(C\), such that both angles are acute and equal.

To make it easier to find appropriate pairs of points, we will order the entire "view" from each vertex. Around each point, we radially sort all outgoing segments, normalize them (by dividing by the greatest common divisor of the coordinates of the vector corresponding to the segment), and group them into buckets with the same direction. For a given vertex, we only need a list of directions and the number of points assigned to each of them. For a fixed \(BC\), let's now choose any normalized direction originating from \(B\) and call its vector \(v\). The direction from \(C\) that can be connected with it to form the letter \(Z\) must have the exact opposite vector, \(-v\). Exactly then, the segments originating from \(B\) and \(C\) are parallel and can become the arms of two equal angles at \(B\) and \(C\).

To additionally enforce that they are acute, we check the sign of the cross product and the positivity of the dot product for vectors \(\overrightarrow{BA}\) and \(\overrightarrow{BC}\) (which allows us to avoid using trigonometric functions or floating-point types). For a given \(BC\), we thus count the pairs \((A, D)\) using the two-pointer technique on the sorted lists. This allows us to count in a single pass all combinations satisfying the strict inequalities, and by repeating this process for all pairs \((B, C)\) we obtain a solution with an \(O(n^3)\) complexity.

\(O(n^2 \log n)\) Time Solution

The \(O(n^3)\) solution utilizes the fact that the "middle" segment well describes a single letter \(Z\), but the number of such segments is too large. In the optimal version, we therefore change our perspective: we iterate not over the middles, but over the directions of the arms of the letter \(Z\). For all pairs of points, we create the segments connecting them, sort them by slope, and work independently within each group of parallel segments.

Within a single group, we want to rotate all segments so that we look at them as horizontal segments. We do this via a linear coordinate transformation corresponding to a rotation of the plane: a pure rotation by an angle \(\varphi\) is described by the formula \[(x', y') = (x\cos\varphi - y\sin\varphi,\; x\sin\varphi + y\cos\varphi).\] In our solution, we choose \(\varphi\) such that the direction of the considered segments is rotated exactly onto the \(OX\) axis; in the implementation, however, we do not explicitly calculate \(\cos\varphi\) and \(\sin\varphi\). Instead, we directly use the directional vector of the segment (its coordinates \((a, b)\)) and treat them as "unnormalized" \(\cos\varphi\) and \(\sin\varphi\). It is important to use the same \(a\) and \(b\) for all points in a single group of parallel segments – only then do we preserve the correct order between them after rotation. In practice, this boils down to a very simple formula \[(x', y') = (ax - by,\; bx + ay),\] which is exactly what appears in the model solution to avoid using floating-point types. In the new coordinate system, each segment is a horizontal interval \([x'_L, x'_R]\) at height \(y'\). Two such segments form the letter \(Z\) exactly when they are at different heights, and the right endpoint of the higher one has a strictly greater \(x'\) than the left endpoint of the lower one.

At this stage, only the order matters, not the specific coordinates, so we compress \(y'\) into numbers from the interval \([1, K]\), where \(K\) denotes the number of different \(y'\) values (heights of horizontal segments) appearing in a given group. Now we can perform a sweep-line algorithm over \(x'\): each "left endpoint" event of a segment at height \(y'\) adds \(1\) in the segment tree at position \(y'\), while a "right endpoint" event reads from the tree the sum on the interval \([1, y'-1]\). This is exactly the number of lower segments that can be connected with the current one into the letter \(Z\). After processing a group of segments, we clear the tree and move to the next slope.

In total, we have \(O(n^2)\) segments, and each update and query in the segment tree takes \(O(\log n)\) time, which, combined with coordinate scaling, yields a complexity of \(O(n^2 \log n)\).