учитывая небольшой набор точек в 2d, как нарисовать круги, которые не перекрываются вокруг каждого из них, чтобы их радиус был максимальным?

Question

У фермера есть n коз. По совпадению у него также есть n фиксированных должностей в области, где он хочет, чтобы козы паслись. Он хочет привязать каждого козла к посту длиной веревки. Он хочет дать каждой козе как можно больше свободы, но козлиные канаты печально известны своей запутанностью, поэтому он не может позволить какой-либо козе иметь возможность бродить по территории другой козлы. Какое максимальное количество веревки он мог бы использовать? (В этой задаче будет не более 50 коз)

Я не знаю, как решить эту проблему, подумав некоторое время. Спасибо за ответы.

(Исходная задача: https://open.kattis.com/problems/goatropes)

Answer 1

Рассмотрим случай, когда только 2 полюса p1, p2 лежат на расстоянии d (1,2). Назовем r1 длину веревки для козла на полюсе 1, r2 длину веревки для козла на полюсе 2. Тогда простое соотношение:

r1 + r2 <= d(1,2)

Если мы добавим третий полюс (и еще одного козла), мы можем добавить еще два отношения:

r1 + r3 <= d(1,3)
r2 + r3 <= d(2,3)

Очевидно, как поступить с n полюсами и n козами. В любом случае это приведет к (n x (n-1)) / 2 неравенствам, как указано выше. Теперь давайте попробуем максимизировать размер всей веревки. Всего веревка будет

R=r1+r2+r3+...+rn

Теперь проблема сформулирована так:

Maximize R=r1+r2+r3+...+rn

С учетом ограничений:

ri + rj <= d(i,j)  where i<j

Это классическая формулировка задачи линейного программирования, поиска Simplex или любого другого подходящего алгоритма.