Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.89/96: Рейтинг темы: голосов - 96, средняя оценка - 4.89
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100

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

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

Студворк — интернет-сервис помощи студентам
люди помогите решить задачу


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

1 1
0 0
1 -1
-1 0

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

НЕВЫПУКЛЫЙ
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
29.10.2008, 16:44
Ответы с готовыми решениями:

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

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

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

32
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.10.2008, 13:51
Студворк — интернет-сервис помощи студентам
Через диагонали самое быстрое, составляешь два уравнения, приравниваешь и находишь координаты пересечения прямых, потом смотришь, попадает ли точка на оба отрезка прямой, т.е. на собственно диагонали. Писать лень, ненавижу эти трехэтажные формулы в математике.
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 13:59
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Program marazm;
function podshet_ugla(xo,yo,x1,y1,x2,y2,xd,yd:real):real;
var a1,a2,ad:real;
begin
{---здесь находим координаты относительно точки угла---}
x1:=x1-xo;
x2:=x2-xo;
xd:=xd-xo;
y1:=y1-yo;
y2:=y2-yo;
yd:=yd-yo;
{---Здесь переводим в полярную систему координат относительно точки угла---}
a1:=arctg(y1/x1);
a2:=arctg(y2/x2);
ad:=arctg(yd/xd);
{---Здесь мы проверяем с помощью вектора диагонали, в какую сторону "смотрит" наш угол---}
if ((ad>a1)and(ad>a2))or((ad<a1)and(ad<a2)) then podshet_ugla:=360-abs(a1-a2)
else podshet_ugla:=a1-a2
end;
begin
end.
Так. это процедура для угла - ща сделаю программу не только для четырехугольников, но и для многоугольников.
решение этой задачи сводится к доказательству того что ни один из углов не является развернутым - т.е. 180гр. или большим ему
для того чтобы понять что за угол перед нами лежит переводим лучи выходящие из этого угла в полярную систему координат из декартовой - получаем углы соответственно.
два луча выходящих из одной точки делят все пространство на 2 части, чтобы понять какая из этих частей принадлежит внутреннему углу многоугольника, смотрим в какую сторону выходит один из лучей его диагоналей
Такое решение приемлемо для любых многоугольников.

Я же вам говорил, что это 5й класс школьной программы геометрии.
Всё гениальное просто )))
0
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 14:02  [ТС]
а можешь написать полностью всю задачу?
P. S. пожалуйста.
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 15:19
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Program marazm;
 
function podshet_ugla(xo,yo,x1,y1,x2,y2,xd,yd:real):real;
var a1,a2,ad:real;
begin
{---здесь находим координаты относительно точки угла---}
  x1:=x1-xo;
  x2:=x2-xo;
  xd:=xd-xo;
  y1:=y1-yo;
  y2:=y2-yo;
  yd:=yd-yo;
{---Здесь переводим в полярную систему координат относительно точки угла---}
  if x1<>0 then a1:=arctg(y1/x1)
    else a1:=pi/2;
  if x2<>0 then a2:=arctg(y2/x2)
    else a2:=pi/2;
  if xd<>0 then ad:=arctg(yd/xd)
    else ad:=pi/2;
{---Здесь мы проверяем с помощью вектора диагонали, в какуч сторону "смотрит" наш угол---}
  if ((ad>a1)and(ad>a2))or((ad<a1)and(ad<a2)) then podshet_ugla:=360-abs((a1-a2)/pi*180)
    else podshet_ugla:=(a1-a2)/pi*180;
end;
 
 
const N=4;
var a:array[1..N,1..2]of real;
       i:integer;
       flag:boolean;
 
 
 
begin
{---Флаг указывает что никаких углов больше 180 градусов нету---}
  flag:= false;
{---Заполнение массива точек---}
  for i:=1 to N do begin
    write('Введите A',i,' x: ');
    readln(a[i,1]);
    write('Введите A',i,' y: ');
    readln(a[i,2]);
  end;
 
{---Просмотр массива точек на предмет выявляения в нем углов >180 градусов---}
  if podshet_ugla(A[1,1],A[1,2],A[2,1],A[2,2],A[N,1],A[N,2],A[3,1],A[3,2])>=180 then flag:=true;
  for i:=2 to N-2 do 
    if podshet_ugla(A[i,1],A[i,2],A[i+1,1],A[i+1,2],A[i-1,1],A[i-1,2],A[i+2,1],A[i+2,2])>=180 then flag:=true;
  if podshet_ugla(A[N-1,1],A[N-1,2],A[N,1],A[N,2],A[N-2,1],A[N-2,2],A[1,1],A[1,2])>=180 then flag:=true;
  if podshet_ugla(A[N,1],A[N,2],A[1,1],A[1,2],A[N-1,1],A[N-1,2],A[2,1],A[2,2])>=180 then flag:=true;
{---Вывод результата---}[/COLOR]
  if flag then wirte('Многоугольник невыпуклый !!!')
    else wirte('Многоугольник выпуклый');
 
readln;
 
end.
PS: Код я писал из башки прямо тут, поэтому могут быть какие либо маленькие ошибки и несоответствия. Паскаля у меня нет, проверить не на чем.
0
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 15:45  [ТС]
он выдаёт ошибку 18:0 деление на 0.
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 15:47
Какая строка ?? напиши на какой строке выдает - посмотрим...
0
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 15:48  [ТС]
В начале 18-ой
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 15:57
Всё понял...
Там нужна доп проверка, чтобы избежать деления на ноль

Добавлено через 59 секунд
*** !!! я что знаю где тут 18я ?)))))
если бы тут была более сложная задача я бы долго её искал... а тут только одно деление - в арктангенсе.

Добавлено через 35 секунд
поэтому надо писать саму строчку - а не её номер!!!)

Добавлено через 33 секунды
сейчас исправлю

Добавлено через 6 минут 21 секунду
Исправил...
А так же исправил обшибку с градусами/радианами
0
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
30.10.2008, 15:59  [ТС]
в функции?
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
30.10.2008, 16:09
Ну и что на этот раз ?
Какие еще ошибки ?

Добавлено через 1 минуту 16 секунд
Цитата Сообщение от Vany Посмотреть сообщение
в функции?
Сам посмотри... я думаю не слепой.
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
31.10.2008, 07:58
Скажи, на чем основан твой метод, ксентар
0
 Аватар для Joker
18 / 18 / 0
Регистрация: 29.10.2008
Сообщений: 100
31.10.2008, 10:25  [ТС]
что такое "ксентар"
0
Of Wolf and Man
 Аватар для Xentar
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
31.10.2008, 12:11
что такое "ксентар"
Это я ))))
Скажи, на чем основан твой метод, ксентар
Смотри - мы берем внутренние углы многогранника, и если он выпуклый, то каждый угол должен быть меньше 180 градусов (т.е. не быть даже развернутым)
Для этого мы перебираем все углы.
Для того чтобы найти углы берем точку и два луча A1, A2 из неё - переводим в полярную систему координат, и считаем разность углов лучей A=A1-A2 - т.е. угол многоугольника - в этом случае мы получаем 2 угла
1й угол = A - то что мы получили взяв разницу углов векторов.
2й угол = 360-A - противоположенный ему угол.
Необходимо определить какой из них принадлежит нашему многоугольнику, для этого берем диагональ D из этой же точки к еще одной из точек нашего многоугольника, и смотрим лежит ли диагональ D между лучами A1 и A2, ежели да, то разница углов лучей A1 и A2 будет уголом нашего многоугольника
Ежели D не находиться в промежутке между A1 и A2 то разность этих углов - внешний угол, а угол нашего многоугольника будет все остальное, окромя разности этих углов 360-(A1-A2)
Таким образом перебираем все углы.
Если какой то из углов >=180 градусов то устанавливаем булевский флаг, сигнализирующий о том что этот многоугольник не является выпуклым.
Вывод решения.

Добавлено через 4 минуты 12 секунд
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
Program marazm;
 
uses crt;
 
{---Здесь считаем угол по триганометрическим формулам---}
function alpha(x,y:real):real;
var a:real;
begin
if x=0 then if y>0 then a:=pi/2
                   else a:=3*pi/2
       else begin
            if (x>0) then
                     if y>=0 then a:=arctan(y/x)
                            else a:=2*pi+arctan(y/x);
            if (x<0) then a:=pi+arctan(y/x);
            end;
alpha:=a;
end;
 
 
function podshet_ugla(xo,yo,x1,y1,x2,y2,xd,yd:real):real;
var a1,a2,ad:real;
temp:real;
begin
{---здесь находим координаты относительно точки угла---}
  x1:=x1-xo;
  x2:=x2-xo;
  xd:=xd-xo;
  y1:=y1-yo;
  y2:=y2-yo;
  yd:=yd-yo;
{---Здесь переводим в полярную систему координат относительно точки угла---}
  a1:=alpha(x1,y1);
  a2:=alpha(x2,y2);
  ad:=alpha(xd,yd);
{---Здесь мы проверяем с помощью вектора диагонали, в какуч сторону "смотрит" наш угол и считаем его---}
  if ((ad>a1)and(ad>a2))or((ad<a1)and(ad<a2)) then temp:=360-abs((a1-a2)/pi*180)
    else temp:=(a1-a2)/pi*180;
    podshet_ugla:=temp;
end;
 
 
const N=4; {изменяя это значение меняешь количество граней, должно быть >=4}
 
var a:array[1..N,1..2]of real;
       i:integer;
       flag:boolean;
 
 
 
begin
clrscr;
{---Флаг указывает что никаких углов больше 180 градусов нету---}
  flag:= false;
 
{---Заполнение массива точек---}
  for i:=1 to N do begin
    write('Введите A',i,' x: ');
    readln(a[i,1]);
    write('Введите A',i,' y: ');
    readln(a[i,2]);
  end;
 
{---Просмотр массива точек на предмет выявляения в нем углов >180 градусов---}
  if abs(podshet_ugla(A[1,1],A[1,2],A[2,1],A[2,2],A[N,1],A[N,2],A[3,1],A[3,2]))>=180 then flag:=true;
  for i:=2 to N-2 do
    if abs(podshet_ugla(A[i,1],A[i,2],A[i+1,1],A[i+1,2],A[i-1,1],A[i-1,2],A[i+2,1],A[i+2,2]))>=180 then
 
flag:=true;
  if abs(podshet_ugla(A[N-1,1],A[N-1,2],A[N,1],A[N,2],A[N-2,1],A[N-2,2],A[1,1],A[1,2]))>=180 then
flag:=true;
  if abs(podshet_ugla(A[N,1],A[N,2],A[1,1],A[1,2],A[N-1,1],A[N-1,2],A[2,1],A[2,2]))>=180 then flag:=true;
 
{---Вывод результата---}
  if flag then write('Вогнутый многогранник !!!')
    else write('Выпуклый многогранник!!!');
 
readln;
 
end.
Добавлено через 8 минут 10 секунд
Я потестил - вроде работает...
Если что не так - пиши при каких значениях не работает - будем смотреть.
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
31.10.2008, 12:11
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
33
Ответ Создать тему
Новые блоги и статьи
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru