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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.11.2010, 16:21
Новичок

Отправить личное сообщение для rv93 Посмотреть профиль Найти все сообщения от rv93
 
Регистрация: 16.11.2010
Адрес: Иваново, Россия
Сообщений: 2

задача на СИ
Многоугольник задан координатами своих вершин при их последовательном обходе. Составить ПОДПРОГРАММУ, определяющую является ли многоугольник выпуклым.

помогите решить, пожалуйста, и если можно с объяснением.
  #2  
Старый 16.11.2010, 16:26
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

наводка: знак векторного произведения векторов двух последовательных сторон должен сохраняться при обходе.
  #3  
Старый 16.11.2010, 16:33
гость

 
Сообщений: n/a

посчитай выпуклую оболочку, если число точек в ней равно числу вершин, значит выпуклый

ПОДПРОГРАММЫ для рассчета выпуклой оболочки общедоступны
  #4  
Старый 16.11.2010, 16:33
Новичок

Отправить личное сообщение для rv93 Посмотреть профиль Найти все сообщения от rv93
 
Регистрация: 16.11.2010
Адрес: Иваново, Россия
Сообщений: 2

совсем не понял
  #5  
Старый 16.11.2010, 16:34
гость

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
наводка: знак векторного произведения векторов двух последовательных сторон должен сохраняться при обходе.
распространенное заблуждение. этого недостаточно. контрпример - пентаграмма
  #6  
Старый 16.11.2010, 17:08
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Сообщение от гость Посмотреть сообщение
распространенное заблуждение. этого недостаточно. контрпример - пентаграмма
Мда, верно, требуется знание, что полигон простой. То же относится и к идее с выпуклой оболочкой.

В Graphics Gems 4 p. 141:
A more efficient convexity test is known that doesn't require a priori knowledge
that P is simple; see e.g. (Moret and Shapiro 1991). It is also based on signed areas.)
Moret and Shapiro Algorithms from P to NP
  #7  
Старый 17.11.2010, 11:50
гость

 
Сообщений: n/a

Выпуклым он будет тогда и только тогда, когда прямые несмежных сторон
не пересекаются.
  #8  
Старый 17.11.2010, 13:07
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Выпуклым он будет тогда и только тогда, когда прямые несмежных сторон
не пересекаются.
неправда. могут и не пересекаться а быть вогнутым
  #9  
Старый 17.11.2010, 14:30
гость

 
Сообщений: n/a

Да, что-то не то сморозил. Можно сделать по определению - записать уравнения каждой прямой, содержащей сторону, в виде ax+by+c=0, подстановкой координат остальных вершин убедиться, что все они попадают в одну полуплоскость.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра