| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > Срочно прога на С нужна |
| Автор: gelo777 29.5.2006, 20:21 |
 Очень прошу, пожалуйста - помогите, не знаю куда уже кинуться, нужна помощь. Написать программу , решающую математическую задачу. Задача: Даны два моножества на плоскости. Выбрать три точки из второго множества таким образом, чтобы составленный из них треугольник полностью накрывал первое множество и его площадь при этом была минимальной. Помогите, плизз! Осталось мало времени  |
| Автор: jxr 29.5.2006, 20:37 |
| Причем здесь С? Надо алгоритм? - есть форум "Алгоритм". |
| Автор: sergejzr 29.5.2006, 20:39 |
| Для домашних заданий, курсовых, существует "Центр Помощи" Тема перенесена! Добавлено @ 20:40 Из С++ |
| Автор: Friackazoid 30.5.2006, 11:57 |
| Уточните каким образом задаются множества. И как должен быть оформлен вывод программы. |
| Автор: nostromo 30.5.2006, 14:34 |
| Алгоритм может быть примерно такой (компромисс между простотой и эффективностью): 1. Строим выпуклую оболочку первого множества и выбрасываем из второго множества все точки, попадающие в нее. 2. Перебираем все пары оставшихся во втором множестве точек и выбираем только те, для которых соответствующий отрезок не пересекает выпуклую оболочку первого множества. 3. В получившемся графе из точек и отрезков ищем циклы длины три, для каждого из них проверяем, что соответствующий треугольник содержит первое множество (достаточно взять одну любую точку первого множества) и вычисляем его площадь. 4. Среди выбранных на предыдущем шаге треугольников выбираем треугольник с минимальной площадью. |
| Автор: gelo777 30.5.2006, 23:56 | ||
| Спасибо огромное! Извини, если что не так.. ТОлько вот бы оченьхотелось на програмный код взглянуь, очень надо..  Добавлено @ 23:59
К сожалению - нужна программа... |
| Автор: DeadSoul 31.5.2006, 00:06 |
| В качестве алгоритма подойдет полный перебор. Код попробуй написать сам. |
| Автор: B3cK 31.5.2006, 02:02 |
| По-моему легче перебором найти треугольники которые покрывают первое множество, после чего отобрать треугольник с наименьшой площадью. Например координаты треугольника: A(Ax,Ay), B(Bx, By), C(Cx,Cy) ну и координата точки для проверки: P(x,y) Тогда: Если все опpеделители | Ax-x Ay-y | | Bx-x By-y | | Cx-x Cy-y | | Bx-x By-y | | Cx-x Cy-y | | Ax-x Ay-y | ненулевые и одного знака, то точка P находится внутpи тpеугольника ABC. Если знак одного отличается от двух дpугих - то снаpужи ABC. Если же хотя бы один из них 0 - то на гpанице. Два нуля - P совпадает с одной из веpшин. Тpи нуля - тpуегольник выpожденный A=B=C=P. |