Цунамі

Країну Картезія можна описати простою декартовою координатною площиною. Вісь $x$ є узбережжям. Позитивна півплощина $y$ — це суша, а негативна півплощина $y$ — це океан. На материку розташовано кілька великих міст, які можна описати координатами $(x,y)$, де y > 0. Іноді в океані біля Картезії трапляються цунамі, які можуть затопити всю країну. Вода починає з y = 0 і просувається рівномірно в додатному напрямку $y$.

Картезія розробляє систему попередження про цунамі. Вона складається з двох компонентів: одного метеорологічного центру, що здатен виявити цунамі заздалегідь, і кабелів, які з'єднують міста прямими лініями (жодного бездротового зв'язку!). Всі кабельні з'єднання можуть передавати попередження майже миттєво.

Місто вважається захищеним, якщо в ньому розташовано метеорологічний центр або якщо воно напряму з'єднане кабелем з іншим захищеним містом (тобто, якщо існує кабельний шлях до метеоцентру через інші міста).

Політика ускладнює задачу! Якщо місто $A$ отримує попередження від міста $B$, а $B$ розташоване далі від узбережжя, ніж $A$, лідери $A$ будуть невдоволені: «Ми ближче до океану, ніж місто $B$, тому попередження мало пройти через нас!» Тому потрібно знайти рішення, де жодне місто не отримує попередження від міста, що далі від узбережжя. (Це означає, що метеорологічний центр має бути у місті, розташованому якнайближче до узбережжя.)

Маючи опис Картезії, знайдіть мінімальну загальну довжину кабелю, що потрібна для створення системи попередження, де всі міста захищені і кожне місто отримує попередження лише через міста, що не далі від узбережжя.