Алгоритмы

[Cris]

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

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

 

[dreamer]

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

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

 

[Cris]

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

ну можещ и разжевать и в желудок положить и код написать
мне б хотяб статии где почитать, или просто написать какието уравнения я там уже решу что нибудь, я покачто дошол до этого:
уравнение касательно для окружности (x0,y0,R) и точки(x1,y1) - лежащей НА ОКРУЖНОСТИ:
(x1-x0)(x-x1)+(y1-y0)(y1-y0)=R^2
для окружности (0,0,R) и ЛЮБОЙ точки на плоскости (x0,y0):
x0*x+y0*y=R^2
и как это связать вмести...
ну можно из (x1-x0)(x-x1)+(y1-y0)(y1-y0)=R^2 сделать уравнение для любой точки через углы, и потом сделать таких два уравнения для одной окружности и другой при неизвестных x,y,x1,y1 и хз как решить
или както сделать два уравнение по второй формуле и потом с какими то высчитанными коефициентами сделать из них одну прямую для двух окружностей

 

[dreamer]

Со ссылкой каждый может, а подумать?
Для окружности (a,b,R₀) уравнение касательной в точке окружности (x₀,y₀):
(x₀ - a)(x - x₀) + (y₀ - b)(y - y₀) = R₀²
Преобразовываешь к виду y = Ax + B, при этом A и B неизвестные, зависящие от x₀ и y₀.
Аналогично делаешь для второй окружности и получаешь уравнение той же касательной (поскольку она общая для обоих окружностей)
y = Cx + D, причем C и D неизвестные и зависят от x₁ и y₁.
Приравниваем A(x₀,y₀)=C(x₁,y₁), B(x₀,y₀)=D(x₁,y₁) (поскольку оба уравнения описывают одну касательную),
добавляем два уравнения окружностей (которые описывают допустимые x₀, y₀, x₁, y₁ для даных окружностей):
A(x₀, y₀) = C(x₁, y₁),
B(x₀, y₀) = D(x₁, y₁),
(x₀ - a)² + (y₀ - b)² = R₀²,
(x₁ - c)² + (y₁ - d)² = R₁².
Получаем четыре уравнения с четырьмя неизвестными, решаем любым из методов, подставляем, получаем A — тангенс угла наклона прямой.

 

[Cris]

Со ссылкой каждый может, а подумать?
Для окружности (a,b,R₀) уравнение касательной в точке окружности (x₀,y₀):
(x₀ - a)(x - x₀) + (y₀ - b)(y - y₀) = R₀²
Преобразовываешь к виду y = Ax + B, при этом A и B неизвестные, зависящие от x₀ и y₀.
Аналогично делаешь для второй окружности и получаешь уравнение той же касательной (поскольку она общая для обоих окружностей)
y = Cx + D, причем C и D неизвестные и зависят от x₁ и y₁.
Приравниваем A(x₀,y₀)=C(x₁,y₁), B(x₀,y₀)=D(x₁,y₁) (поскольку оба уравнения описывают одну касательную),
добавляем два уравнения окружностей (которые описывают допустимые x₀, y₀, x₁, y₁ для даных окружностей):
A(x₀, y₀) = C(x₁, y₁),
B(x₀, y₀) = D(x₁, y₁),
(x₀ - a)² + (y₀ - b)² = R₀²,
(x₁ - c)² + (y₁ - d)² = R₁².
Получаем четыре уравнения с четырьмя неизвестными, решаем любым из методов, подставляем, получаем A — тангенс угла наклона прямой.

хм.. ну что ж попробуем спс большое

 

[Cris]

такс делаю очередную задачу:
есть некий отрезок времени, и есть дополнительные отрезки на этой временной шкале которые использовать нельзя - т.е. прерывают любое действие
и у нас есть действие которое можно делать за время T с качеством 1, за 2T с качеством 2, 4T - с качеством 3, и есть количество таких одинаковых действий, нужно сказать с каким максимальным качеством можно выполнить все эти действия?
может хоть подскажите в каком направлении думать
я предполагаю что это динамическое программирование, но как его сделать пока что не думаеться както

 

[dreamer]

такс делаю очередную задачу:
есть некий отрезок времени, и есть дополнительные отрезки на этой временной шкале которые использовать нельзя - т.е. прерывают любое действие
и у нас есть действие которое можно делать за время T с качеством 1, за 2T с качеством 2, 4T - с качеством 3, и есть количество таких одинаковых действий, нужно сказать с каким максимальным качеством можно выполнить все эти действия?
может хоть подскажите в каком направлении думать
я предполагаю что это динамическое программирование, но как его сделать пока что не думаеться както

Непонятно как-то объясняешь
Из того, что я понял все выглядит довольно просто — есть набор допустимых отрезков (время между отрезками, которые использовать нельзя) в которые нужно вложить сначала максимальное количество отрезков по 4Т, потом в оставшееся место по 2Т и Т. Если этого мало то начинаем дробить отрезки по 4Т на двое, если и этого мало — дробим еще 2Т.

 

[Cris]

Непонятно как-то объясняешь
Из того, что я понял все выглядит довольно просто — есть набор допустимых отрезков (время между отрезками, которые использовать нельзя) в которые нужно вложить сначала максимальное количество отрезков по 4Т, потом в оставшееся место по 2Т и Т. Если этого мало то начинаем дробить отрезки по 4Т на двое, если и этого мало — дробим еще 2Т.

то есть отталкиваться от жадного алгоритма? я пока хочю сделать перебор - рекурсию

 

[dreamer]

то есть отталкиваться от жадного алгоритма? я пока хочю сделать перебор - рекурсию

Задача не выглядит достаточно сложной для этого.
Если бы размеры были фиксированы то была бы задача рюкзака, а так вещи можно делить.