Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.57/46: Рейтинг темы: голосов - 46, средняя оценка - 4.57
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
1

Определить, образуют ли точки выпуклый четырехугольник

29.10.2008, 16:44. Просмотров 8618. Ответов 32
Метки нет (Все метки)

люди помогите решить задачу


Даны координаты четырех точек (x1,y1), (x2,y2), (x3,y3), (x4,y4). Необходимо определить, образуют ли они выпуклый четырехугольник.
Ввод :
координаты точек в порядке обхода.
Вывод :
ответ в виде 'ВЫПУКЛЫЙ'/'НЕВЫПУКЛЫЙ'.
Пример
Пример ввода:

1 1
0 0
1 -1
-1 0

Пример вывода:

НЕВЫПУКЛЫЙ
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.10.2008, 16:44
Ответы с готовыми решениями:

Образуют ли 3 точки треугольник
Ввести числа x1,y1,x2,y2,x3,y3 которые являются значениями координат трех точек на "плоскости."...

Определить, образуют ли точки вершины квадрата
Даны координаты x1y1 x2y2 x3y3 x4y4, нужно определить образуют ли они квадрат.

Три точки заданы координатами. Определить, образуют ли они треугольник
Три точки заданы координатами. Определить, образуют ли они треугольник program treugolnik;...

Четырехугольник задан координатами своих вершин составить программу которая определяет какой это четырехугольник
Помогите пожалуйста

Создают ли точки плоскости выпуклый многоугольник
Создают ли точки плоскости, координаты которых хранятся в двух массивах, выпуклый многоугольник. ...

32
Xentar
Of Wolf and Man
994 / 190 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
29.10.2008, 17:23 2
Это мат-задача... ща вспомню геометрию 5го класса
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
29.10.2008, 17:26  [ТС] 3
так ты поможешь???
0
Xentar
Of Wolf and Man
994 / 190 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
29.10.2008, 17:35 4
Прямоугольник считается выпуклым, когда, при вписывании его в окружность, все углы прямоугольника будут находиться на линии окружности.
Прямоугольник можно вписать в окружность, когда сумма его противоположенных углов = 180 градусам

A+C=B+D=180

Подумай как решить. Приду домой напишу задачу. - проверишь
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
29.10.2008, 17:49  [ТС] 5
Я просто не знаю как найти градусы углов.
0
Varlock
365 / 68 / 2
Регистрация: 25.09.2008
Сообщений: 401
29.10.2008, 18:01 6
Xentar, мне кажется что вы неправы
я конечно могу ошибаться, но далеко не каждый выпуклый четырёхугольник может быть вписан в окружность
безусловно, что когда его можно вписать в окружность он выпуклый, но вот если он выпуклый не факт, что его можно вписать в окружность...
пример:
возьмум ромб с координатами:
(5,0)(0,1)(-5,0)(0,-1)
и попробуйте мне сказать что он не выпуклый, или что его можно вписать в окружность если всё же считаете, что можно, скажите мне координаты центра окружности и радиус

Vany, лично у меня пока не появилось в голове простых идей как решить эту задачу...=))
есть одна идея, как решать в лоб, но она, ИМХО, не слишком проста в реализации...(мне лично писать на её основе что-либо лень =))
собственно вот какая она:
1)вспоминаем, что если четырёхугольник выпуклый, то отрезки его диагоналей пересекуться.
2)вспоминаем векторную алгебру, а точнее способы перехода к новой системе координат (я на память формул не напишу, суть в том, что мы поворачиваем систему на какой-то угол, и меняем координаты нуля... формулы в инете найти можно, там они простые через синус косинус насклько я помню...)
3)берём первую диагональ(именно диагональ, т.е. точки которые вводили через одну), и считаем вектор, который его задаёт(имея координаты это просто).
4)после этого переходим к нокой системе координат(пересчитываем по формулам координаты всех 4-ёх точек), таким образом, чтобы этот вектор совпадал с осью Х.
5)получаем: 2 точки лежат на этом векторе, а 2 нет. у тех, которые на нём не лежат, проверяем координаты У. Если одна положительна а вторая отрицательна, то продолжаем дальше. Если они обе по одну сторону от оси, то значит четырёхугольник невыпуклый.
6)аналогично поступаем со второй диагональю... точно так же переходим, чтобы она совпала с осью Х и проверяем, пересекаются ли они....
если обе проверки дали пересечение, значит диагонали пересекаются, значит выпуклый.
Если нет, то нет...+)

7)можно придумать ещё несколько промежуточных проверок, которые ещё раньше отсекут невыпуклые четырёхугольники, но имхо, хватит и такого алгоритма

про реализацию подумай лучше сам, там только тригонометрия фактически и минимальное понимание векторной алгебры...+)) все формулы в инете находятся, а большая часть расчётов копипастом делается

З.Ы. я неправильно сказал=)) не не слишком проста в реализации, а недостаточно коротка и элегантна, как лично мне хотелось бы... +)
1
Xentar
Of Wolf and Man
994 / 190 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
29.10.2008, 18:03 7
возьми 3 точки
смести систему координат относительно центральной
это будет точка угла
две другие будут точки образующие углы с осью Ох
с помощью несложных тригенометрических функций ты сможешь это найти.
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
29.10.2008, 18:04  [ТС] 8
да но я не знаю тригенометрию
0
Xentar
Of Wolf and Man
994 / 190 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
29.10.2008, 18:05 9
Xentar, мне кажется что вы неправы
да - черт тебя дери - ты прав
Обшибся я ....
помню что решал такую задачу, но как не помню...
1
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
29.10.2008, 18:10  [ТС] 10
А как найти градусную меру угла???
0
MadMag
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.10.2008, 03:29 11
Градусную меру угла? какого? зная что?
Угла этого прямоугоьника?

Добавлено через 5 минут 45 секунд
А у меня такая идея, простая в реализации, которую я реализую, по определению, вспомним геометрию.
выпуклый многоугольник это многоугольник, такой что отрезок образованный любыми точками этого прямоугольника лежит всеми точками в прямоугольнике, следовательно
мы находим, вектора, ллежащие между противоположными точками, а затем берем середины веторов, смотрим, лежат ли они в прямоугольнике, если лежат, то он выпуклый....другое дело как определить эти точки....есть идейка конешно, щас подумаю...

Добавлено через 2 минуты 7 секунд
хотя я тогда не уверен в ответе, там не очень точный, максимум скока там....17 знаков послле запятой?

Добавлено через 4 минуты 12 секунд
А! идея!!!
находим смотрим какая точка выше, какая ниже, какая левее, какая правее, затем.
Верхняя и нижняя должны лежать по оси игрек выше и ниже отрезка соединяющего левую и правую, а правая и левая должны лежать правее и левее по оси икс от соответсвующего отрезка

Добавлено через 1 минуту 24 секунды
мой способ не красть))
я решаю))

Добавлено через 4 часа 52 минуты 33 секунды
сложно млин
0
Xentar
Of Wolf and Man
994 / 190 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 12:55 12
Цитата Сообщение от YeLLoW DucK Посмотреть сообщение
такой что отрезок образованный любыми точками этого прямоугольника
1) не отрезок, а диагонали. AC и BD
ибо отрезки AB, BC, CD, DA - являются сторонами прямоугольника.
2) эта задача решается проще. Так ты её будешь решать целую вечность

Добавлено через 1 час 11 минут 48 секунд
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 13:07  [ТС] 13
Просто подскажите как найти градусы угла.
0
Puporev
Модератор
56327 / 43111 / 29821
Регистрация: 18.05.2008
Сообщений: 102,449
30.10.2008, 13:11 14
Четырехугольник является выпуклым когда его диагонали пересекаются.
Следовательно нужно составить уравнения прямых, проходящих через точки 1 и 3, 2 и 4. Приравнять их и решить полученное уравнение. Если есть корень и притом 1, то да, иначе нет.
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 13:16  [ТС] 15
Да но надо в многоугольнике.

Добавлено через 2 минуты 25 секунд
И кстати как узнать пересекаются они или нет???
0
Puporev
Модератор
56327 / 43111 / 29821
Регистрация: 18.05.2008
Сообщений: 102,449
30.10.2008, 13:17 16
Определить, образуют ли точки выпуклый четырехугольник
Это Ваше задание, или мое?
0
Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 13:18  [ТС] 17
Моё, но помогите пожалуйста.:'(:'(:'(
0
MadMag
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.10.2008, 13:24 18
Да, пупорев, как написать уравнение диагонаей?
0
Puporev
Модератор
56327 / 43111 / 29821
Регистрация: 18.05.2008
Сообщений: 102,449
30.10.2008, 13:29 19
Посмотри в школьном учебнике по геометрии, или в инете ""уравнение прямой, проходящей через 2 точки.
0
MadMag
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.10.2008, 13:45 20
Варлок прав, про переход в новую систему координат, а потом просмотр новых координат.
Люди, кто сможет это реализовать?
http://e-science.ru/math/theory/?t=275
здесь описано....как раз наш случай

Добавлено через 1 минуту 34 секунды
Ой, сорри пупорев, я конечно ступил
0
30.10.2008, 13:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2008, 13:45

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

Нарисовать четырехугольник минимальной площади, охватывающий все заданные точки
Даны координаты (х,у) 100 точек. Необходимо нарисовать четырехугольник минимальной площади,...

Проверить, образуют ли 4 точки (x, y) выпуклый четыреухгольник
Если точки в любом порядке. Помогите, пожалуйста(( Я знаю как проверить если точки упорядочены, но...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru