» Помогоите решить олимпиадную задачу

Задача звучит приблизительно так.
Жила-была "Звезда смерти" (наверное Deathstar из Star Wars). И решила она пальнуть по планетах, но так, чтобы за один выстрел зацепить как можно больше планет. Собственно говоря и надо расчитать как ей надо пальнуть и сколько планет она зацепит (только максимум). Вообщем надо найти максимальное количество шариков, через которые проходит прямая
Входные условия: Количество планет, координаты их центров и их радиусы, звезда может стрелять из любой точки.

Помогите пожалуста решить, т.к. я уже долго над мучаюсь, а придумать ничего не могу.
Изначально задача должна была быть решена в 3D. Но в принципе для начало сдалось бы её решить на координатной плоскости (2D).

Зарание спасибо!!!

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

если радиусы действительно лишние -- "стрельба" сводится к нахождению максимального числа точек на одной линии

Цитата:

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

Еслиб были точки так бы и сказали, но это жырные планеты по которым не обязательно попадать точно в центр.

ScipionST
Выскажи мудрую теорию, что луч звезды смерти, встретив на своём пути одну планету и уничтожив её дальше не пройдёт .... Но это так
А один из алгоритмов такой:
Массив с координатами планет. По очереди (перебирая все) строишь прямую между двумя планетами и считаешь на какой прямой их больше. Всё.

Можно попробовать решить задачу в лоб - т.е. прострелять во все направления с каким-то шагом, а затем посмотреть сколько максимально планет зацепило. Не изящно конечно, зато очень жизненно

Kotzillo
Теперь посчитай на поле (2D) 200*200 в 16 направлениях

на плоскости - делим зону обстрела на большое число частей (например 720 - по полградуса),
заводим соотв массив.
от каждой планеты проводим две прямые - от одного края и от другого, соотв. получаем два угла , a1 и a2 , в нашем массиве во всех эдементах от а1 до а2 увеличиваем счётчик.
После перебора всех планет, просто выбираем в массиве элемент с наибльшим счетчиком и в том направлении бахаем.
Для 3d можно решить аналогично - небольшую сферу вокруг нас делим по плоским пятигранникам, каждый из них делим еще на маленькие кусочки. Вычисляем проекции от планет на эти кусочки - и вперед точно также...только геометрии будет побольше..

max0z
Зачем всё так сложно?

ScorpionST
А можно всё таки прямо текст задачи сюда (оригинал), сдается мне что что-то недоопределено, слишком много степеней свободы для просто олимпиадной задачи. Скорее всего звезда, которая стреляет находится в какой-то точке, которая задана.


Добавлено:
KADABRA
что значит прямую между планетами? а радиусы?

Добавлено:
maxoz
а из какой точки стрелять то? автор утверждает, что звезда может находиться где угодно. Вот если её местонахождение задано, тогда ваша идея близка к верной (хотя работать ваш алгоритм не будет, но направление мышления верное

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


Добавлено:
FuzzyLogic
интерестно почему алгоритм работать не будет ?
--
если звезда может быть где угодно, то применяем етот алгоритм к любой планете,
получаем вектор..разместим звезду на этом векторе как можно дальше (чтобы все планеты были в одну сторону и пальнем..

max0z
Если задано откуда стрелять, тогда решается так (для 2D):

Пусть есть N планет

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

2. Каждая и этих касательных однозначно определяется углом (угол допустим, относительно оси x). Таким образом, для каждой планеты мы нашли интервал [угол1,угол2] в который надо стрелять чтобы попасть в планету.

3. Располагаем все эти интервалы на отрезке [0,360градусов] и ищем интервал который пересекает максимальное кол-во интервалов [угол1,угол2]. Делается это элементарно - сортируем все углы по возрастанию, а потом просто пробегаем по ним, ведя счетчик: если угол является углом1 (то есть начало интервала для одной из планет), то счетчик увеличивается, иначе - уменьшается. Таким образом мы выделим интервал на котором значение счетчика максимально (счетчик - колво сбитых планет), в любом направлении из этого интервала можно стрелять.
Кстати, тут надо учесть что интервал у нас "зацикленный", т.е. может получиться так что некоторые интервалы откроются, но не закроются. Но это уже тонкости реализации.


Добавлено:

Цитата:

интерестно почему алгоритм работать не будет ?

А как вы собрались определять шаг (почему полградуса?) одна планета может иметь радиус 1000000 единиц, а другая 0.000001, тоже самое и с расстояниями ... и чего делать?

Добавлено:
max0z я вам даже картинку нарисовал

Представьте что эти прямые выходят из одной точки (звезды смерти), которая находится далеко (внизу-слева) и угол между этими прямыми 0.00000001 градуса

Добавлено:
KADABRA

Цитата:

Зачем всё так сложно?

Ну подскажите как сделать просто

FuzzyLogic
Да. Некая сложность есть. Но есть и несколько альтернативных методов решения. И всё-таки некоторая погрешность может быть допушена.

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

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

А какой контур? Описаный вокруг всех планет? Дело в том что касательные могут пересечься до того как пересекут контур. Я тоже думал где-то в том направлении, но потом порисовал, и мне показалось что не получается ... хотя может я и не прав.

FuzzyLogic
значит задача стоит в поиске этих отрезков, а может областей! Дальше уже твоя логика поиска

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

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

Sleepwalker
Ну я почему и сказал ... как-то не очень похоже на олимпиадную задачу, ни по ресурсоемкости, ни по затратности с точки зрения программирования (обычно любая олимпиадная задача должна писаться за 30 минут, а тут что-то как-то не очень похоже, особенно в 3D случае Т.е. либо что-то не так в условиях, либо всё таки есть хитрое решение.

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

Координаты точек внешних сторон шаров даны. A(a,b)
Координаты точек прямых даны. B(c,d)
sqrt( (a-c)^2+(b-d)^2 )<=сигма (Теорема пифагора)

Для плоскости можно попробовать и вот так :
1) ищем прямую расстояния от которой до центров планет минимальны.. ( метод наименьших квадратов для F(x)=ax+b;
2) из тех планет которые прямая не пересекла исключаем одно, расстояние от поверхности которой до этой прямой максимально (самую дальнюю планету исключаем)
3) если прямая проходит не через все оставшиеся поланеты - возвращаемся к шагу 1.
4) на полученной прямой размещаем ЗВЕЗДУ так чтобы все планеты были по одну сторону..ЗАЛП.

для 3d то-же самое..
алгоритм получается почти линейный , но сложно доказуемый ;-(

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

Добавлено:
В любом случае.
Можно решать системы 2-х уравнений вида

|уравнение прямой
|
|уравнение окружности
|

Цитата:

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

DeathStar - космический корабль из Звёздных Войн размером с нехилую планету и обладающий лазероподобным оружием разрывающим планету за 1 удар.

Sleepwalker
В вашем алгоритме вы будете искать пересечения углов (эдаких треугольников) на вхождение друг в друга, образованные парами касательных между парами окружностей. Или я не правильно понял?


Цитата:

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

Function
Вы о чём? Краткость конечно сестра таланта, но мысли надо выражать так чтобы и другим было ясно, иначе не стоит их и писать.

И про пересечения тоже ... Sleepwalker не спрашивал как ишется пересечение окружности с прямой, ему надо пересекать "углы" или в случае 3D эдакие конусы, если я правильно понял его идею.

vhl
Каких отрезков? Вы не ответили по поводу контура, пересечение с каким контуром вы ищете... И если это контур который вмещает в себя все планеты, то тогда если касательные пересекутся до пересечения с контуром, то полученный отрезок - чепуха.


Цитата:

алгоритм получается почти линейный , но сложно доказуемый

Угу, и создается ощущение что работать он тоже не будет. Хотя, пока не опровергнут ...

Насчёт недосказаного в условии задачи - все даные, что были - представлены в первичном условии, было бы конечно хорошо если бы было известно откуда должна стрелят звезда смерти, но несудьба.
Насчёт погрешности ничего сказать не могу, т.к. в примере входных и результирующих даных писалися координаты планет аля (1.00;5.00), а радиус 2.0 и т.д., ну а ответ - собственно просто 2 или 3 ....

Насчет ограничения по времени - до 3 секунд.

FuzzyLogic
Ну я тоже пришел к тому, что и не в контуре дело и даже не в области максимального числа пересечений областей, потому как можно придумать такой расклад, что данная точка не будет лежать на искомой прямой да и по поводу алгоритма max0z тоже самое можно сказать - расположи планеты в 2 линии и найденая вашим алгоритмом прямая будет лежать между ними.

Занятная задача...

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

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

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

Вроде должно работать...

А может надо считать плотность планет в определенном направлении или что-то в этом роде. Ведь по условию расчет должен быть быстрым.

vhl

Цитата:

тоже самое можно сказать - расположи планеты в 2 линии и найденая вашим алгоритмом прямая будет лежать между ними

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

Я лично конешно думал сделать через метод найменьших квадратов, тобиш нарисовать прямую с минимальным отклонением от центров планет, но есть одно НО!!!

Были бы планеты квадратами(кубами) - задачу можно было бы довольно легко реализовать, но в случае кругов, максимально допустимое отклонение проведенной линий варьируется и зависит от радису планет и угла между линией и осями координат.