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

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


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

1 1
0 0
1 -1
-1 0

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

НЕВЫПУКЛЫЙ

0

Это мат-задача... ща вспомню геометрию 5го класса

0

так ты поможешь???

0

Прямоугольник считается выпуклым, когда, при вписывании его в окружность, все углы прямоугольника будут находиться на линии окружности.
Прямоугольник можно вписать в окружность, когда сумма его противоположенных углов = 180 градусам
A+C=B+D=180

Подумай как решить. Приду домой напишу задачу. - проверишь

0

Я просто не знаю как найти градусы углов.

0

Xentar, мне кажется что вы неправы
я конечно могу ошибаться, но далеко не каждый выпуклый четырёхугольник может быть вписан в окружность
безусловно, что когда его можно вписать в окружность он выпуклый, но вот если он выпуклый не факт, что его можно вписать в окружность...
пример:
возьмум ромб с координатами:
(5,0)(0,1)(-5,0)(0,-1)
и попробуйте мне сказать что он не выпуклый, или что его можно вписать в окружность если всё же считаете, что можно, скажите мне координаты центра окружности и радиус

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

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

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

З.Ы. я неправильно сказал=)) не не слишком проста в реализации, а недостаточно коротка и элегантна, как лично мне хотелось бы... +)

1

возьми 3 точки
смести систему координат относительно центральной
это будет точка угла
две другие будут точки образующие углы с осью Ох
с помощью несложных тригенометрических функций ты сможешь это найти.

0

да но я не знаю тригенометрию

0

Xentar, мне кажется что вы неправы

да - черт тебя дери - ты прав
Обшибся я ....
помню что решал такую задачу, но как не помню...

1

А как найти градусную меру угла???

0

Градусную меру угла? какого? зная что?
Угла этого прямоугоьника?

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

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

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

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

Добавлено через 4 часа 52 минуты 33 секунды
сложно млин

0

Сообщение от YeLLoW DucK такой что отрезок образованный любыми точками этого прямоугольника

1) не отрезок, а диагонали. AC и BD
ибо отрезки AB, BC, CD, DA - являются сторонами прямоугольника.
2) эта задача решается проще. Так ты её будешь решать целую вечность

Добавлено через 1 час 11 минут 48 секунд

0

Просто подскажите как найти градусы угла.

0

Четырехугольник является выпуклым когда его диагонали пересекаются.

Следовательно нужно составить уравнения прямых, проходящих через точки 1 и 3, 2 и 4. Приравнять их и решить полученное уравнение. Если есть корень и притом 1, то да, иначе нет.

0

Да но надо в многоугольнике.

Добавлено через 2 минуты 25 секунд
И кстати как узнать пересекаются они или нет???

0

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

Это Ваше задание, или мое?

0

Моё, но помогите пожалуйста.:'(:'(:'(

0

Да, пупорев, как написать уравнение диагонаей?

0

Посмотри в школьном учебнике по геометрии, или в инете ""уравнение прямой, проходящей через 2 точки.

0

Варлок прав, про переход в новую систему координат, а потом просмотр новых координат.
Люди, кто сможет это реализовать?
http://e-science.ru/math/theory/?t=275
здесь описано....как раз наш случай

Добавлено через 1 минуту 34 секунды
Ой, сорри пупорев, я конечно ступил

0