Мм

таким образом у нас есть двумерная функция, нужно найти её максимум

У нее дофига локальных максимумов

ну или тогда попробовать другое решение

разбить пространство на клетки

плоскость то есть

и для середины каждой клетки посчитать n

выбрать максимальное n

Это не ответ

У этой задачи точно в общем случае не одно решение

ну и что? Я ж про то, что мой воображаемый алгоритм вероятностный

приблизительный - ответ

Ты можешь не попасть в максимум

А надо точный

ну не в максимум проще всего отжигом

это зависит от мелкости разбиения на клетки

там вообще даже думать особо не надо )

Отжиг хорош, но он тоже неточный

во, можно методом каких-нибудь последовательных приближений искать локальные максимумы. Сначала побить на клетки, потом от клеток ползти к максимумам, потом выбрать лучший из них

100x(0,0),100x(0,2),r=1

Отжиг хорош, но он тоже неточный

ну а я про что )

Тут отжиг не сможет

цели то не могут в одной точке находиться

цели разве могут быть в одной и той же координате

цели разве могут быть в одной и той же координате

Ок, +-0.0000001

(ну окей, посчитаем, что там в дельте)

ну это бред

не бред

в реальности такого не будет

Задача не про реальность

это эдакая эмуляция веса

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

условно, в одной базе находится 300 танчиков, а в другой 10

общее число кусков не более, чем 2 в степени Н

можно их просто все перечислить и все.

ну вот это и есть близко расположенные точки

воо, нарисовать что-то вроде матрицы инцидентности, где 1 означает, что эти обе цели можно накрыть одним разом

общее число кусков не более, чем 2 в степени Н

Ты 2^n кусков перебирать будешь?

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

это и есть что я сказал 8)

кк )

Это куб?

Как пропатчить питон под кде?

ставь из портов.

можно создать пространственную структуру данных

число различных наборов пересечений это экспонента

чтобы это быстрее посчитать

число различных наборов пересечений это экспонента

чо?

для 3 точек у нас есть область, где ноль окружностей, три по одной, три по 2, одна на все 3

Мы же берем все точки пересечения и их проверяем, разве нет?

восемь

Точек квадрат

в квадрат же укладываемся, не?

для 4 точек будет уже 16 разных вариантов. Каждая точка плоскости либо лежит в окрестности цели Х, либо нет. Итого по биту на каждую цель. Экспонента

Для каждой точки нужно еще ответ найти за линию

для 4 точек будет уже 16 разных вариантов. Каждая точка плоскости либо лежит в окрестности цели Х, либо нет. Итого по биту на каждую цель. Экспонента

Зачем тебе все варианты перебирать?

А можно ещё применить пчелиный алгоритм А к нему уже кластеризацию

Для каждой точки нужно еще ответ найти за линию

в хэше хранить точки пересечения со счётчиком

точек пересечения не больше чем 2n**2

в хэше хранить точки пересечения со счётчиком

Для новой точки ты не знаешь ответ, а все пересечения могут быть разными

а, не, то решение что я придумал не катит %)

я пока формализовал, понял, что хрень

эмм

а почему бы не перейти в полярные координаты?

ERROR: S client not available

взять окружность в которую попадают все точки

эмм, зачем?

такой нет

такой нет

с чего бы вдруг?

данного радиуса нет

какие характеристики имеет максимальное скопление точек, которое вписывается в окружность радиуса R?

данного радиуса нет

причём тут радиус? у тебя есть множество точек. ты просто подбираешь окружность в которую попадают вообще все.

по в первых, если найти точки, которые лежат на границах выпуклого многоугольника, который эти точки покрывает

ок, и зачем?

причём тут радиус? у тебя есть множество точек. ты просто подбираешь окружность в которую попадают вообще все.

у ракеты ограничен радиус поражения же

ок, и зачем?

найти центр системы отсчёта.

найти центр системы отсчёта.

и как это поможет?

то расстояние между двумя самыми удалёнными точками этого многоугольника будет меньше либо равно 2R

у ракеты ограничен радиус поражения же

да.

алгоритм такой, циклом пробегаем по всем точкам

ок, и зачем?

да ты ваще сиреневый на кодефорсезе, а до сих пор тут чо то думаешь. Где AC?

да ты ваще сиреневый на кодефорсезе, а до сих пор тут чо то думаешь. Где AC?

я за куб знаю, а сиреневый это дно

для каждой точки находим все точки которые не далее чем 2R до исходной точки

я раньше желтым был

я раньше желтым был

не красный – значит не нужен

и потом проверяем можем ли мы вписать из граничного многоугольника из этих точек в окружность радиуса R

(там ведь как на топкодере?)

красные задроты

и потом проверяем можем ли мы вписать из граничного многоугольника из этих точек в окружность радиуса R

яннп

а сиреневые нет, угу

яннп

яннп?

сиреневый изи

и потом проверяем можем ли мы вписать из граничного многоугольника из этих точек в окружность радиуса R

угу, и что нам это даёт?

2 задачи решаешь