![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
![]()
Добрый день.
Даны координаты 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. Причина: Дополнение условия |
![]() |
![]() |
![]() |
#2 | ||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,544
|
![]() Цитата:
Цитата:
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 20.08.2014 в 11:28. |
||
![]() |
![]() |
![]() |
#3 | |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
![]() Цитата:
Дело в том, что этот многоугольник должен состоять лишь из указанных точек. Вот рисунок, описывающий пример. ![]() ABCD - это МВО, ACD - это один из многоугольников, удовлетворяющих условию задачи. Последний раз редактировалось Demius; 20.08.2014 в 12:46. |
|
![]() |
![]() |
![]() |
#4 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,544
|
![]()
имеем выпуклый многоугольник включающий в себя все точки.
Значит мы можем от него только отрезать. максимальный из оставшихся будет если отрежем минимальный. Мы можем отрезать любой многоугольник. Любой многоугольник (из отрезанных) можно нарезать на треугольники, каждый из который будет удовлетворять условию задачи и иметь меньшую площадь. Значит отрезаем треугольник. Минимальный треугольник который мы можем отрезать соединяет три последовательные вершины.(т.к. МВО). проверяем перебором и выбираем. Цитата:
Минимальный треугольник ДВЕ последовательные вершины исходного + одна точка внутри(ближайшая к прямой проходящей через наши вершины). если таких нет, то первоначальный вариант (три вершины). P.S. три вершины это тоже две +одна точка внутри (только "внутри" включает и границы). из МВО следует что ближайшие к прямой и являющиеся вершинами оболочки будут "ближайшими" (соседними) вершинами.
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 20.08.2014 в 15:03. |
|
![]() |
![]() |
![]() |
#5 |
Пользователь
Регистрация: 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 ![]() Будет ли работать на этом примере ваш алгоритм эффективно? |
![]() |
![]() |
![]() |
#6 | ||||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,544
|
![]() Цитата:
Цитата:
Цитата:
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. |
||||
![]() |
![]() |
![]() |
#7 |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
![]()
Спасибо. Попробую реализовать.
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
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 |