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

ScipionST

Цитата:

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

Сам то понял что сказал ?
Как раз с кругами то и проще круг одинаково распёрт в разные стороны - просто отожравшаяся точка Ту же задачу но с квадратами/кубами аналитичеким методом будет гоораздо сложнее - только у сферы/шара проекция одинакова с любой стороны

max0z
А я вам снова картинку нарисовал

Пара пояснений к картинке... слева имеем кластер планет (скажем 1000 штук) с оооочень маленькими радиусами, такие, что какую бы прямую мы не провели она проходит максимум через две планеты. Кластер этот представляет эдакое облако вытянутое по вертикали. Справа имеем N планет, через которые мы запросто можем провести прямую.

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

Как чел, имеющие прямое отношение к олимпиадному программирование могу предложить такое решение (вернее такое решение я со своими учениками придумали на кружке):

0 Будем пользоваться методом динамического программирования

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

2 В результатет 1) получили соответствие пара <-> множество
3 Далее формулируем след утверждение, что точка Х лежит на прямой А_1А_2А_3 ... А_n т. и т.т. если она находится в соотношении 2) со всеми возможными парами из А_1А_2А_3 ... А_n

4 Нашли самую длинную последовательность планет

Осталось найти эту самую прямую - задача аналитической геометрии на прикладной математике за 2 курс

Критика поощряется )

Критика:

1. Для каждой пары чего чего?
2. Соответствие - пара чего <-> множество опять же чего (точек, прямых, плоскостей, шаров?, ....)
3. Т.к. 1 и 2 непонятны, то, честно говоря, непонятно и что утверждается.
4. после более подробного изложения 1 2 3

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

max0z
Конечно есть.
Сводится она, в общем, к следующему (напишу для плоскости).
1. Для множества S окружностей (s1, s2, ..., sN), заданных уравнениями:
(x1-a1)^2 + (y1-b1)^2 = с1^2
....
(xN-aN)^2 + (yN-bN)^2 = cN^2
определить, существует ли прямая ax + by + z = 0, которая пересекает каждую сферу из заданного множества S. + И найти один из вариантов a, b и z (само собой их может быть много).
Если данная задача решается, то исходная решается перебором. Для оптимизации можно вместо перебора строить дерево решений - задачу можно свести к следующей. Есть множество S1 окружностей для которых такая прямая существует. Определить существует ли она для множества S2 полученного из S1 добавлением еще одной окружности.

На предыдущей странице FuzzyLogic описал как это сделать. Т.е. основная идея (FuzzyLogic - сорри, я немного с другой стороны подойду) - записываем уравнение прямой в виде y = ax + b. Собственно нас интересует коэффициент a - он определяет угол наклона. Для двух окружностей получим интервал - [a1, a2] - он описывает угол наклона всех прямых проходящих одновременно через обе окружности. Если такая прямая существует для множества окружностей S, то пересечение множества соответствующих интервалов углов наклона прямых непустое. При добавлении новой окружности - просто осуществляем эту проверку.

Дальше можно перейти от плоскости к 3-х мерному пространству, - будет достаточно решать данную задачу для проекций шаров на плоскости X Y Z (одновременно). Т.е. при добавлении новой сферы - рассчитываем ее проекции на каждую из плоскостей и в каждой из них проверяем описанное выше условие. Если во всех 3 ответ утвердителен, то такая прямая существует.

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

Надеюсь что нигде не ошибся

А как вам такое, правда, не знаю толком, как развить до победного конца.

Немного проанализировав ситуацию можно смело полагать, что Звезда Смерти стреляет непосредственно из планеты.
Сортируем планеты по возрастанию диаметров.
Встаём в самую маленькую и палим в крайние точки самой большой. Проверяем сектор обстрела. Нет, блин, сильно много проверок получается... Ещё обратный сектор обстрела проверить, в каждом секторе найти оптимальную прямую, потом последовательно прострелять во все планеты по мере уменьшения их диаметров и повторить это всё для следующей из массива... Нет, однозначно много - в 3 секунды вряд ли уложишься, если планет достаточно много.

Промежуточный алгоритм ( сокращение полного перебора с N ! до N*(N-1)*(N-2) )
Перебор можно значительно сократить основываясь на факте, что
луч сначала попадает в одну планету, потом задевает еще несколько и наконец выходит через последню.(как минимум в две планеты мы попадём точно)

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

Дело за малым

to RedMac
Согласен. ИМХО, если учитывать ограничения по тайту и памяти, то динамика наиболее применима. У меня идея решения очеь похожа на твою.

автору:
Если в динамическом программировании силен - попробуй этот метод.

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

Задача №1
Решить систему ленейных уровнений
| A1X + B1Y + C1Z + D1 = 0
< A2X + B2Y + C2Z + D2 = 0
| A3X + B3Y + C3Z + D3 = 0


A1 = -1 A2 = 0 A3 = -0.5
B1 = 0 B2 = 1.5 B3 = 1
C1 = -1.79 C2 = 8.7 C3 = 3.5
D1 = 4.2 D2 = -2.25 D3 = 0.6


Задача №2
Решить систему ленейных уровнений
K1X1 + L1X2 + M1X3 + N1X4 + S1 = 0
K2X2 + L2X2 + M2X3 + N2X4 + S2 = 0
K3X3 + L3X3 + M3X3 + N3X4 + S3 = 0
K4X4 + L4X4 + M4X4 + N4X4 + S4 = 0


K1 = 0 K2 = 1 K3 = 2 K4 = 2
C1 = 8 C2 = 12 C3 = -1 C4 = 7
M1 = 4.2 M2 = 0 M3 = 2.5 M4 = -3
N1 = -4.2 N2 = 0.5 N3 = 0 N4 = 0
S1 = 0 S2 = -3.6 S3 = -5.5 S4 = 0


Задача №2
Решить систему ленейных уровнений
E1X + F1Y + G1Z + H1U + A1 = 0
E2X + F2Y + G2Z + H2U + A2 = 0
E3X + F3Y + G3Z + H3U + A3 = 0
E4X + F4Y + G4Z + H4U + A4 = 0


L1 = 4.5 L2 = 0 L3 = 6.5 L4 = -4.5
F1 = -4.7 F2 = -9.2 F3 = 8.1 F4 = 7.3
G1 = 0 G2 = -4.7 G3 = 0 G4 = 1.5
H1 = 2 H2 = -4 H3 = 0 H4 = 0
A1 = 0.9 A2 = -1.4 A3 = -6.5 A4 = 3

Зарание благодорю за помощь! Если чтото надо по дизайну обращайтесь

DIMICH
А решать на каком языке программирования? Определись с языком и напиши в соответствующую прибитую тему данного раздела (прямо наверху: задачи на C/C++, задачи на Pascal, итд)

DIMICH
Что то я не понял, в чём тут проблема может быть.
Обычные линейные уравнения: из 1го выделяем Х определённый через Z и Y, подставляем во второе, из него получаем Y выраженный через Z и подставляем в 3. Вторая задача аналогично. Програмно решается простым перебором.
А вот про окружности надо подумать. Задача в концу концов сводится к планиметрии. Надо найти множество точек попадающих в пересечения заданных окружностей, вернее даже найти координаты фигуры, точки которой будут находится в пределах максимального количества пересекающихся окружностей. Вот приобрёл себе очередную головную боль, уж больно я задачи всякие люблю

07.12.07
Решил задачу для системы из 2х планет. Для большего количества решается рекурсией.
Если такие задачи люди решают на олимпиадах за 30 минут с выходом готового кода - снимаю шляпу.

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

Я решал нечто подобное. Если не брать во внимание радиусы (то есть работать с точками). Разбиваем все точки на пары точек. Например, три точки: 1, 2, 3 разбиваются на 1 - 2, 1 - 3, 2 - 3. Пара точек - это некоторая прямая, проходящая через них, характеризующаяся в системе координат двумя параметрами - a и b (y = ax + b). Находим для всех пар эти a и b, занося их в отведенный массив (массив структур, т.е. a и b - это один элемент массива). Далее сортируем этот массив. В итоге, пробежав по массиву мы можем найти самую длинную последовательность пар точек, лежащих на одной прямой (то есть последовательность элементов с одинаковыми а и одинаковыми b в отсортированном массиве). Зная это число (число пар) можно определить и число точек, лежащих на одной прямой. Для не точек а шаров все аналогично, разве что при нахождении последовательности a и b сверяются не жестко а с учетом радиуса.

Параметр a для пары точек p1 и p2 считается так: a = (p1.y - p2.y) / (p1.x - p2.x);
b = p2.y - a*p1.x;

массивов должно быть как минимум два. Первый это массив пар. Второй - это массив отрезков. Они взаимосвязаны.