Почти выпуклые многоугольники: олимпиадная задача на плоскости

Пусть $P_1, P_2, \dots, P_n$ – данные точки ($n = 1 000 000$), а $H = H_1H_2 \dots H_k$ – их выпуклая оболочка. Будем называть точки $H_1$, $H_2, \dots, H_k$ внешними, а остальные $n - k$ точек внутренними.

Пусть $Q_1$, $Q_2, \dots, Q_n$ такая перестановка точек $P_1$, $P_2, \dots, P_n$, что $Q = Q_1Q_2 \dots Q_n$ – почти выпуклый многоугольник. Из сторон многоугольника $H$ ровно одна, назовем ее $s$,не является стороной $Q$.

Пусть $R$ – вершина $Q$, для которой внутренний угол $Q$ больше $180^\circ$. Тогда $R$ – внутренняя точка, а все остальные внутренние точки лежат внутри треугольника, с вершиной $R$ и противоположной стороной $s$.

Если внутренняя точка единственна, она должна совпадать с $R$. Тогда любую сторону $H$ в качестве $s$ и мы получим $n - 1>10$ способов построить многоугольник $Q$ – противоречие.

Если есть ровно две внутренних точки – $R_1$ и $R_2$, то в качестве $R$ можно взять любую из них. Пусть, например, $R \equiv R_1$. Тогда $s$ – та сторона $H$, которую пересекает луч $R_1R_2$. Если это сторона $H_uH_{u + 1}$, то $Q$ совпадает с одним из двух многоугольников $H_1H_2 \dots H_uR_1R_2H_{u + 1} \dots H_k$ или $H_1H_2 \dots H_uR_2R_1H_{u + 1} \dots H_k$. Таким образом, в этом случае для $Q$ есть лишь четыре варианта.

Наконец, рассмотрим случай, когда внутренних точек хотя бы три. Пусть $G = G_1G_2 \dots G_m$ – их выпуклая оболочка.

Назовем вершину $G_i$ многоугольника $G$ перспективной, если лучи $G_iG_{i - 1}$ и $G_iG_{i + 1}$ пересекают одну и ту же сторону $H$. (Считаем, что $G_0 \equiv G_m$ и $G_{m + 1} \equiv G_1$.) Любая вершина $G_i$, которую можно выбрать в качестве $R$, должна быть перспективной. Однако, не каждая перспективная $G_i$ может быть взята как $R$.

Покажем, что у $G$ не больше трех перспективных вершин. Действительно, предположим, что таких вершин не меньше четырех. Обозначим какие-то четыре из них через $A$, $B$, $C$, $D$ так, что $ABCD$ – выпуклый четырехугольник с $\angle A + \angle B \ge 180^\circ$. Тогда луч $BC$ лежит внутри угла, образованного лучами $AB$ и $AD$. Так как $A$ – перспективная, все три луча пересекают одну и ту же сторону $H$.

Но $B$ тоже перспективная, поэтому лучи $BA$ и $BC$ также пересекают одну сторону $H$. Поскольку лучи $AB$ и $BA$ не могут пересекать одну сторону $H$, получено противоречие.

Пусть теперь $G_l$ – перспективная вершина $G$, а лучи $G_lG_{l - 1}$ и $G_lG_{l + 1}$ пересекают сторону $H_uH_{u + 1}$ многоугольника $H$.

Рассмотрим луч $r$ с вершиной $G_l$. Будем вращать $r$ вокруг $G_l$ внутри угла $G_{l - 1}G_lG_{l + 1}$ от луча $G_lG_{l-1}$ до $G_lG_{l+1}$. Пусть $J_1\equiv G_{l-1}$, $J_2, \dots, J_{n-k-1}\equiv G_{l+1}$ – отличные от $G_l$ внутренние точки, через которые проходит $r$ при этом вращении. Обозначим также $J_0\equiv H_u$ и $J_{n-k}\equiv H_{u+1}$. Тогда, для некоторого $0\le v\le n-k-1$ получаем, что $$Q \equiv H_1H_2 \dots H_{u-1}J_0J_1 \dots J_vG_lJ_{v+1}J_{v+2}\dots J_{n-k}H_{u+2}H_{u+3}\dots H_k.$$

Рассмотрим несамопересекающийся многоугольник $Q' = H_1H_2 \dots H_{u-1}J_0J_1 \dots J_{n-k}H_{u+2}H_{u+3}\dots H_k.$

Так как $Q'$ невыпуклый, у него есть угол, больший $180^\circ$. Поскольку его внутренние углы в вершинах $H_1$, $H_2, \dots, H_u \equiv J_0$, $H_{u+1} \equiv J_{n-k}, \dots, H_k$ меньше $180^\circ$, то для некоторого $1\le w\le n-k-1$ угол $Q'$ в вершине $J_w$ больше $180^\circ$. Тогда $v=w-1$ или $v=w$. (Иначе у $Q$ будет два угла, больших $180^\circ$, в вершинах $G_l$ и $J_w$.) Значит для каждой перспективной вершины $G_l$ многоугольника $G$ есть не больше двух вариантов $Q$, а общее количество почти выпуклых многоугольников не превосходит $3\cdot 2 = 6 < 10$.