ИОИП: Заключительный этап ИОИП 2022

Канеки смотрит на неориентированный граф на плоскости из \(n\) вершин и \(m\) ребер. В этом графе ему интересно найти самого большого дракона.

Назовем сегментом дракона три ребра графа \(AL\), \(AB\) и \(AR\), имеющие общую вершину \(A\), и обладающие следующими свойствами:

• \(0 < \measuredangle (BAL) < 45^\circ\) и направление поворота от \(\overrightarrow{AB}\) к \(\overrightarrow{AL}\) — по часовой стрелке;
• \(0 < \measuredangle (BAR) < 45^\circ\) и направление поворота от \(\overrightarrow{AB}\) к \(\overrightarrow{AR}\) — против часовой стрелки;
• \(|AB| \geqslant |AL|\) и \(|AB| \geqslant |AR|\), то есть \(AB\) — максимальное по длине из трех ребер.

При выполнении всех указанных условий вершины \(A\) и \(B\) называются началом и концом сегмента, а ребра \(AL\), \(AB\) и \(AR\) — левой лапой, основанием и правой лапой сегмента, соответственно.

Определим дракона как последовательность сегментов, в которой

• начало первого сегмента \(A_1\), также называемое головой дракона, находится в вершине \(S\);
• \(A_{i} = B_{i-1}\) для всех \(i > 1\), то есть начало каждого следующего сегмента совпадает с концом предыдущего;
• \(\left|\measuredangle \left(\overrightarrow{A_{i-1} B_{i-1}}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ\), то есть угол между векторами оснований соседних сегментов строго меньше \(45^\circ\);
• \(\left|\measuredangle \left(\overrightarrow{A_1 A_i}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ\), то есть угол между вектором от головы дракона \(A_1\) до начала сегмента и основанием сегмента строго меньше \(45^\circ\).

Обратите внимание, что здесь углы взяты по модулю, то есть каждый следующий сегмент может быть повернут относительно предыдущего на менее чем \(45^\circ\) как по, так и против часовой стрелки.

Мощностью дракона будем считать сумму квадратов длин оснований его сегментов, то есть \(\sum |A_i B_i|^2\). В заданном графе помогите Канеки найти дракона максимальной мощности с головой в вершине \(S\).