Ответ 1

Ansatz

Метод грубой силы будет проверять все возможные деления...

Прежде всего следует отметить, что точная ориентация линии не имеет значения. Его всегда можно сместить на небольшие суммы, и есть случаи с более чем одним минимумом. Что важно, какие города идут на ту сторону королевства. Даже когда вы просто пытаетесь использовать все такие возможные комбинации, их нетрудно найти. Для этого я предлагаю следующий алгоритм:

Как найти все возможные подразделения

• Для каждой пары городов x и y линия, соединяющая их, делит королевство на "левый" и "правый". Затем рассмотрим все возможные комбинации слева, справа, x и y:

  • left + x + y vs right (C)
  • left + x vs right + y (A)
  • left + y vs right + x (D)
  • left vs right + x + y (B)

На самом деле я не уверен на 100%, но я думаю, что таким образом вы можете найти все возможное деление с конечным числом испытаний. Поскольку города не имеют размера (я предполагал 0 радиус), линия, соединяющая х и у, может быть слегка смещена, чтобы включить либо город по обе стороны от него.

Один пример счетчика, где этот простой метод, безусловно, будет терпеть неудачу, когда более 2 городов лежат по прямой.

Пример

На этом рисунке показан один шаг моего алгоритма для примера из OP. x и y - два города с 1 жителем. На самом деле с этой парой городов можно получить все возможные дивизии. (Однако 3 балла тривиально, так как нет никаких геометрических ограничений на то, какие комбинации возможны. Интересно, что только начиная с 4 пунктов их местоположение на самолете действительно имеет значение.)

Колинеарные точки

После некоторого обсуждения и плодотворных комментариев я пришел к выводу, что коллинеарные точки не являются проблемой. Нужно просто рассмотреть эти моменты при оценке 4 возможных делений (для каждой пары точек). Например. предположим, что в приведенном выше примере есть еще одна точка в (-1,2). Тогда эта точка будет лежать слева для A и C и справа для B и D.

Ответ 2

Для каждого угла A рассмотрим семейство параллельных прямых, которые образуют угол A с осью x, с особым случаем A=0, соответствующим семейству прямых, параллельных оси X.

Учитывая A, вы можете использовать бинарный поиск, чтобы найти строку в семье, которая разделяет королевство почти одинаково. Таким образом, мы имеем функцию f от углов до целых чисел, отображая каждый угол A до минимального значения |a-b| для строк в семействе, соответствующих A.

Сколько углов нам нужно попробовать? Ситуация существенно меняется только тогда, когда A - это угол, соответствующий линии между двумя точками, угол, который я назову "угол прыжка". Функция непрерывна и, следовательно, постоянна, от углов прыжка. Нам нужно попробовать прыгать под углами, о которых около n choose 2, не более 500 000. Нам также нужно попробовать интервалы углов между углами прыжка, удвоив размер до 1 000 000.

Вместо углов, вероятно, более разумно использовать наклоны. Мне просто нравится думать о углах.

Временная сложность этого подхода O(n^2 log n), n^2 для числа углов log n для двоичного поиска. Если мы сможем узнать больше о функции f, можно будет использовать более быстрый метод, чтобы свести к минимуму f, чем проверять каждую возможность. Например, представляется разумным, что минимум f можно найти под углом, не равным углу скачка.

Также можно устранить бинарный поиск, используя центр тяжести городов. Вычислим средневзвешенное значение

(a1(x1,y1) + a2(x2,y2) + ... + an(xn,yn))/(a1+a2+...+an)

Я думаю, что линии, балансирующие население, пройдут через этот момент. (Хм). Если это так, нам нужно только подумать о углах.

Ответ 3

Случай, когда n меньше 3

В базовом случае есть два города: в этом случае вы просто берете перпендикулярную линию на линии, соединяющей два города.

Случай с тремя или более городами

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

Почему это работает

Если вы разделите число городов на две части, есть как минимум одна половина с двумя или более городами. Для этой части есть две точки, наиболее близкие к границе. Независимо от того, проходит ли граница "очень близко" к этой линии или имеет одну и ту же линию, не имеет значения; потому что "немного другое касание" не поменяет никакого города (в противном случае эти города были не самыми близкими). Поскольку мы пытаемся "каждая граница", мы в конечном итоге создадим границу с указанной касательной.

Пример:

Скажите, что у вас есть следующий сценарий:

1
\
2\ 1

С цифрами, показывающими значения. В этом случае двумя ближайшими точками на границе являются верхняя и правая. Таким образом, мы строим линию, которая указывает на 45 градусов вниз. Теперь мы используем бинарный поиск, чтобы найти наиболее оптимальный раскол: мы поворачиваем все точки, заказываем их по возрастанию, поворачивая x-значение, а затем выполняем бинарный поиск по весам. Оптимальным является разбиение его между началом и двумя другими точками.

Теперь с четырьмя точками:

1    2

2    1

Здесь мы рассмотрим следующие строки:

\ 1\|/2 /
 \ /|\ /
----+----
 / \|/ \
/ 2/|\1 \

И это вернет горизонтальную или вертикальную линию.

Существует единственная возможность - как указано @Nemo, что все эти точки лежат на одной линии. В этом случае нет тангенса, который имеет смысл. В этом случае можно также использовать перпендикулярный тангенс.

псевдокод:

for v in V
    for w in V\{v}
        calculate tangent
        for tangent and perpendicular tangent
            rotate all points such that the tangent is rotated to the y-axis
            look for a rotated line in the y-direction that splits the cities optimal
return the best split found

Кроме того, как почти все геометрические подходы, этот метод может страдать от того, что несколько точек расположены в одной строке, и в этом случае путем добавления простого вращения можно либо включить/исключить одну из точек. Это действительно грязный взломать проблему.

Эта программа Haskell вычисляет "оптимальное направление" (если указанное решение правильное) для данного списка точек:

import Data.List

type Point = (Int,Int)
type WPoint = (Point,Int)
type Direction = Point

dirmul :: Direction -> WPoint -> Int
dirmul (dx,dy) ((xa,ya),_) = xa*dx+ya*dy

dirCompare :: Direction -> WPoint -> WPoint -> Ordering
dirCompare d pa pb = compare (dirmul d pa) (dirmul d pb)

optimalSplit :: [WPoint] -> Direction
optimalSplit pts = (-dy,dx)
    where wsum = sum $ map snd pts
          (dx,dy) = argmin (bestSplit pts wsum) $ concat [splits pa pb | pa <- pts, pb <- pts, pa /= pb]

splits :: WPoint -> WPoint -> [Direction]
splits ((xa,ya),_) ((xb,yb),_) = [(xb-xa,yb-ya),(ya-yb,xb-xa)]

bestSplit :: [WPoint] -> Int -> Direction -> Int
bestSplit pts wsum d = bestSplitScan cmp ordl 0 wsum
    where cmp = dirCompare d
          ordl = sortBy cmp pts

bestSplitScan :: ((a,Int) -> (a,Int) -> Ordering) -> [(a,Int)] -> Int -> Int -> Int
bestSplitScan _ [] l r = abs $ l-r
bestSplitScan cmp ((x1,w1):xs) l r = min (abs $ l-r) (bestSplitScan cmp (dropWhile eqf xs) (l+d) (r-d))
    where eqf = (==) EQ . cmp (x1,w1)
          d = w1+(sum $ map snd $ takeWhile eqf xs)

argmin :: (Ord b) => (a -> b) -> [a] -> a
argmin _ [x] = x
argmin f (x:xs) | (f x) <= f ax = x
                | otherwise = ax
    where ax = argmin f xs

Например:

*Main> optimalSplit [((0,0),2),((0,1),1),((1,0),1)]
(-1,1)
*Main> optimalSplit [((0,0),2),((0,1),1),((1,0),1),((1,1),2)]
(-1,0)

Таким образом, направление - это линия, в которой, если линия перемещает один элемент влево, она также перемещает один элемент в верхнюю часть. Это первый пример. Во втором случае он выбирает линию, которая перемещается в направлении x, поэтому она разбивается по горизонтали. Этот алгоритм допускает только целые точки и не учитывает незначительную настройку линии в случае, если точки помещаются на одну и ту же строку: все они находятся внутри или полностью для параллельной линии.

Ответ 4

[ Изменить: Полужирный текст относится к проблемам, высказанным ранее в комментариях.]

[ Изменить 2: Как я уже указывал ранее, этот ответ является дополнением к более раннему ответу tobi303, который дает аналогичный алгоритм. Основная цель заключалась в том, чтобы показать, что основная идея этого алгоритма является звуковой и достаточно общей. Несмотря на незначительные различия в деталях алгоритмов, предложенных в двух ответах, я думаю, что тщательное чтение раздела "почему это работает", применяемое к любому алгоритму, покажет, что алгоритм на самом деле завершен.]

Если все города находятся в одной прямой линии (включая случай, когда это только один или два города), то решение прост. Я предполагаю, что вы можете обнаружить и решить этот случай, так что остальная часть ответ будет касаться всех других случаев.

Если есть более двух городов, и они не все коллинеарны, решение "грубой силы":

for each city X, 
  for each city Y where Y is not X
    construct a directed line that passes through X and then Y.
    Divide the cities in two subsets: 
    S1 = all the cities to the left of this line
    S2 = all the other cities (including cities exactly on the line)
    Evaluate the "unfairness" of this division.

Среди всех подразделений городов, найденных таким образом, выберите ту, которая имеет наименьшую несправедливость. Верните разницу. Готово.

Обратите внимание, что найденная таким образом линия не является линией, которая делит города "справедливо"; он просто параллелен некоторой такой линии. Если бы нам пришлось найти фактическую разделительную линию, нам пришлось бы сделать еще немного работы, чтобы выяснить где именно поставить эту параллельную линию. Но запрашиваемое возвращаемое значение является просто | a-b |.

Почему это работает:

Предположим, что линия L1 делит города как можно более справедливо. Это не уникальная линия, которая делает это; будет (математически) бесконечное число строк которые достигают такого же "лучшего" разделения, но такие линии существуют, и все, что нам нужно предположить, состоит в том, что L1 является одной из этих строк.

Пусть город A будет ближе всего к L1 на одной стороне линии и город B ближе всего к L1 с другой стороны. (Если A и B не идентифицированы однозначно, то есть если есть два или более городов с одной стороны L1, которые привязаны к "ближе всего к L1", мы можем установить L2 = L1 и перейти к процедуре для L2 ниже.)

Рассмотрим вращения L1 в каждом направлении, используя точку, где L1 пересекает линия AB как точка поворота. По меньшей мере, в одном направлении вращения, повернутое изображение L1 "ударит" по одному из других городов, назовите его C, не касаясь ни A, ни B. (Это следует из того, что города не все вдоль одной линии.) В этот момент C ближе к изображению L1, чем A или B (в зависимости от того, что из этих городов находится на той же стороне от оригинала L1, что и C). Теорема о среднем значении исчисления говорит нам, что в какой-то момент вращение, C было точно так же близко к повернутому изображению L1 как город А или В, в зависимости от того, что находится на той же стороне этой линии.

Это показывает, что всегда существует линия L2, которая делит города насколько это возможно, так что существуют два города: D и E, на той же стороне L2 и привязан к "ближайшему городу до L2" среди всех города на той стороне L2.

Теперь рассмотрим две направленные линии через D и E: L3, проходящие через D, а затем E и L4, который проходит через E, а затем D. Города, которые находятся на другой стороне L2, чем D и E, состоят либо из все города слева от L3 или все города слева от L4. (обратите внимание, что это работает, даже если L3 и L4 пройти через более чем два города.)

Процедура, описанная ранее, - это просто способ найти все возможное строки , которые могут быть строкой L3 или строкой L4 при любом выполнении этого процедура, начинающаяся с линии L1, которая решает проблему. (Обратите внимание, что, хотя всегда есть бесконечные возможные варианты L1, каждый такой L1 приводит к линиям L3 и L4, выбранным из конечного набора линии, которые проходят через два или более городов.) Таким образом, процедура найдет разделение городов, описанных L1, который является решением проблемы.