Hardprob/Minimum Length Triangulation — различия между версиями

Текущая версия на 21:26, 17 апреля 2023

Коллекция пар целых, задающих координаты на плоскости.
Найти триангуляцию набора точек из C, т.е. коллекция E непересекающихся отрезков соединающих некоторые точки из C, так, что внутренность этой выпуклой оболочки подразделена на треугольники.
Минимизировать округленно-евклидову длину триангуляции, т.е.

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Коллекция <m>C=\{(a_i,b_i) : 1 \leq i \leq n\}</m> пар целых, задающих координаты на плоскости.
+* Коллекция <m>C=\{(a_i,b_i) : 1 ≤ i ≤ n\}</m> пар целых, задающих координаты на плоскости.
 * Найти триангуляцию набора точек из <em>C</em>, т.е. коллекция <em>E</em> непересекающихся отрезков соединающих некоторые точки из <em>C</em>, так, что внутренность этой выпуклой оболочки подразделена на треугольники.
 * Минимизировать округленно-евклидову длину триангуляции, т.е.
 <m>
   \begin{displaymath}
-\left\lceil\sum_{((a_i,b_i),(a_j,b_j)) \in
+\left\lceil\sum_{((a_i,b_i),(a_j,b_j)) ∈
-E}\sqrt{(a_i-a_j)^2+(b_i-b_j)^2}\right\rceil.
+E}\sqrt{(a_i-a_j)^2+(b_i-b_j)^2}\right\rceil → \min.
 \end{displaymath}
 </m>
@@ Строка 12: / Строка 12: @@
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+<!-- * {{has-testdata-and-visualization}} -->
+<!-- * {{has-pyomo-model}} -->
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>