Денис Смірнов
Позначимо за S(i, j) площу багатокутника P_i, P_{i+1}, \dots, P_j (iндекси тут i далi беруться за модулем ). Позначимо увесь багатокутник за P = P_1 \dots P_n, тодi S(P) = S(i, j) + S(j, i). В задачі нас просять мінімізувати |S(i, j) - S(j, i)|. Помітимо, що S(i, j) = S(i, j - 1) + S(P_iP_{j-1}P_j) > S(i, j-1), а значить S(i, j) - S(j, i) = 2S(i, j) - S(P) — зростаюча функція за . Це означає, що вона має не більше ніж дві підозрілі на мінімум модулю точки: останню точку P_{j_1}, для якої S(i, j_1) \leq S(j_1, i), і першу точку P_{j_2}, для якої S(i, j_2) \geq S(j_2, i) (j_1 \leq j_2 \leq j_1 + 1). Помітимо що остання умова означає, що S(i, j_1) \leq \frac 12 S(P), а S(i, j_2) \geq \frac 12 S(P).
Таким чином, для кожного нам достатньо розглянути не більш ніж дві точки — P_{j_1} і P_{j_2}. Помітимо, що \frac 12 S(P) \geq S(i, j_1) = S(i+1, j_1) + S(P_i P_{i+1} P_{j_1}) > S(i+1, j_1), а отже при збільшенні , j_1 могла тільки збільшиться, аналогічно j_2. Будемо проводити операцію млина: збільшувати усі індекси , j_1, j_2 та оновлювати відповідь щоразу коли ми отримаємо валідну трійку: так як кожного разу кожен індекс ми змінюємо на одиницю, то будемо підтримувати і S(i, j_1) - S(j_1, i), і S(i, j_2) - S(j_2, i).
Складність розв'язку — : усі позиції , j_1, j_2 в сумі зроблять приблизно один оберт (бо після нього це повинні бути ті самі j_1, j_2 що були для першої розглянутої вершини та не більше одного оберту на пошук перших значень.