Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.08.2014, 15:21   #1
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию Задача на геометрию (Delphi, C++)

Добрый день.

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

Пример входных данных
4
1.0 1.0
-1.0 1.0
-1.0 -1.0
1.0 -1.0
4.0

Пример выходных данных
2.0


Необходим самый эффективный алгоритм решения.

Последний раз редактировалось Demius; 20.08.2014 в 12:37. Причина: Дополнение условия
Demius вне форума Ответить с цитированием
Старый 20.08.2014, 11:11   #2
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,544
По умолчанию

Цитата:
Необходимо вывести максимально возможную площадь многоугольника
Цитата:
Пример выходных данных
2
а я нашел больший.
Изображения
Тип файла: jpg 11.JPG (11.1 Кб, 86 просмотров)
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 20.08.2014 в 11:28.
evg_m вне форума Ответить с цитированием
Старый 20.08.2014, 12:35   #3
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

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

Вот рисунок, описывающий пример.


ABCD - это МВО, ACD - это один из многоугольников, удовлетворяющих условию задачи.

Последний раз редактировалось Demius; 20.08.2014 в 12:46.
Demius вне форума Ответить с цитированием
Старый 20.08.2014, 13:26   #4
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,544
По умолчанию

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

Цитата:
Минимальный треугольник который мы можем отрезать соединяет три последовательные вершины.(т.к. МВО).
НЕВЕРНО!
Минимальный треугольник ДВЕ последовательные вершины исходного + одна точка внутри(ближайшая к прямой проходящей через наши вершины).
если таких нет, то первоначальный вариант (три вершины).

P.S. три вершины это тоже две +одна точка внутри (только "внутри" включает и границы).
из МВО следует что ближайшие к прямой и являющиеся вершинами оболочки будут "ближайшими" (соседними) вершинами.
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 20.08.2014 в 15:03.
evg_m вне форума Ответить с цитированием
Старый 20.08.2014, 17:29   #5
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

Пример входных данных
9
-2.0 2.0
2.0 -2.0
-2.0 -2.0
2.0 2.0
0.0 0.0
1.0 1.0
-1.0 1.0
-1.0 -1.0
1.0 -1.0
1.00008

Пример выходных данных
1.0



Будет ли работать на этом примере ваш алгоритм эффективно?
Demius вне форума Ответить с цитированием
Старый 21.08.2014, 09:42   #6
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,544
По умолчанию

Цитата:
Необходимо вывести максимально возможную площадь многоугольника
Цитата:
Пример выходных данных
1.0
Цитата:
получившегося изменением границы МВО и состоящего из указанных точек, не превышающую S.
L(ABCD)=(2-(-2))*4 =16
L(HEI)=(1-(1))+sqrt(2)*2=2+1,4*2=4,8
L2-L1=16-4,8 >S =1,00008

Цитата:
Будет ли работать на этом примере ваш алгоритм эффективно?
по сравнению с полным перебором вариантов да.
Но есть еще куда стремиться.
В анализе нигде не учитывается что изменение должно быть <S.
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 21.08.2014 в 10:07.
evg_m вне форума Ответить с цитированием
Старый 25.08.2014, 11:12   #7
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

Спасибо. Попробую реализовать.
Demius вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
C++ Задача на геометрию UaKot Помощь студентам 0 12.07.2013 16:03
задача на геометрию Tattoquardas Паскаль, Turbo Pascal, PascalABC.NET 3 09.11.2011 19:42
Задача на геометрию k1r1ch Помощь студентам 16 01.12.2009 22:40
Пожалуйста, помогите решить геометрию Emi Свободное общение 8 21.05.2009 11:45