Помогите написать алгоритм. Задание:
Можна ли с круглой заготовки радиуса r вырезать две прямоугольные пластины с размерами a*b і c*d?

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

Для ответа "можна" надо, чтобы фигура, образованная двумя прямоугольниками, могла быть вписана в окружность радиуса r.


Присоединённый файл ( Кол-во скачиваний: 2 )
 r.JPG

podval
Определение радиуса описанной окружности - имхо более сложная задача. Хотя тоже простая .

Цитата(Akina @ 25.10.2004, 08:37)

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

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

Цитата(Kaskad @ 26.10.2004, 22:02)

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

Ну и как он определит, помещается оставшийся кусок или нет?

Как решил бы я

Оба прямоугольника влезают в окружность если A1-D1, A2-D2 и А1-D2 меньше диаметра окружности.

Надеюсь как все расстояния найти знаешь .

Это сообщение отредактировал(а) Perchilla - 26.10.2004, 22:58

Чесно говоря, как найти А1-D2 понятия не имею

Цитата

Чесно говоря, как найти А1-D2 понятия не имею

По теореме Пифагора

Я в школе плохо учился! Можно конкретную формулу?!

A1-C1 + A2-C2 - один катет
(A1-B1 + A2-B2) / 2 - второй катет
A1-D2 - гипотенуза

Я немного подумал... Существует некий диапазон значений при которых данным методом задача не решается . Вобщем я тебе мозги запудрил, нечайно .

Это сообщение отредактировал(а) Perchilla - 28.10.2004, 19:39

Чтобы уж окончательно запудрить всем мозги вот другое решение:

Приложим обе вершины большей стороны большего прямоугольника к окружности. Пусть центр окружности будет в начале координат, а одна из вершин большего прямоугольника в точке (R;0):

Теперь найдем координаты точки A1 (A1M- это у нас высота, следовательно A1M = A1(y) ; M(x) = A1(x) ). Пусть α = угол A1-O-B1.

Не буду разворачивать последнюю формулу, тут и так все понятно

Теперь достроим больший прямоугольник и найдем координаты остальных точек:

Составим систему уравнений из уравнений окружностей с центрами A1 и B1, и длинами A1C1 и B1C1 соответственно. Это нам нужно для того, чтобы найти точки пересечения двух окружностей, одна из которых будет С1.

получим две точки, но выберем ту, что ближе к центру основной окружности.
Аналогично находим координаты D1.

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

Для начала найдем координаты точки E, являющейся центром отрезка С1-D1:
E(x)=C(x)+(D(x)-C(x))/2
E(y)=C(y)+(D(y)-C(y))/2

Чтобы найти координаты точек A2, B2 можно решить систему уравнений из прямой, проходящей через точки С1 и D1, и уравнения окружности, центр которой является точка E, а радиус – A2-E.

Таким образом получаем 2 пересечения окружности и прямой – 2 точки A2 и B2.

Аналогично большому прямоугольнику находим координаты точек C2 и D2, только из двух возможных точек выбираем те, что дальше от большого прямоугольника.

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

Perchilla
Во ты заморочился... в то время как

Цитата

Оба прямоугольника влезают в окружность если A1-D1, A2-D2 и А1-D2 меньше диаметра окружности.

есть почти правильное решение - только слово "меньше" надо заменить на "не больше". И после корректировки - самое вычислительнобыстрое.

Цитата(Perchilla @ 28.10.2004, 19:43)

Я немного подумал... Существует некий диапазон значений при которых данным методом задача не решается

Сколько смотрел и так и сяк - не нашёл такого...

Задача решается. Окружность радиуса r находится в центре координат (т.О).

(Смотри рисунок)
Один прямоугольник имеет стороны L и H (L >= H), второй l и h (l >= h).
Поместим первый прямоугльник в окружность так, чтобы вершины на стороне L касались окружности. Расстояние по оси OY до сторон длиной L будет соответственно a и b, a+b=H. Причем, b может быть отрицательным в случае a>H (Ну и Бог с ним).
a:=SQRT(r*r-L*L/4);
b:=H-a;
Тогда расстояние от O до дальней стороны l второго прямоугольника
R1:=h+b;
Тогда расстояние от точки O до дальней вершины второго прямоугльника (жирная линия) будет равно
SQRT(R1*R1+l*l/4);
оно должно быть меньше или равно радиусу окружности r.

Это сообщение отредактировал(а) Alex101 - 29.10.2004, 11:12