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

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

29.10.2008, 16:44. Показов 20482. Ответов 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
64319 / 47615 / 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
Ответ Создать тему
Новые блоги и статьи
Контроль уникальности строк в табличной части документа
Maks 18.06.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .
Клиент
Uhbif79 18.06.2026
Здесь простой клиент для работы с сервером.
Сервер
Uhbif79 18.06.2026
Выкладываю простейший сервер.
Дефенестрация
kumehtar 18.06.2026
Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))
Дихотомия добра и зла
kumehtar 18.06.2026
Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .
Своя Интернет-Компания
iceja 18.06.2026
Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .
24 Мат модель здравосохранения: функциональные требования к строительству пищеблока
anaschu 18.06.2026
СРесурсами1: финансовый SD-контур, калькулятор функциональных требований пищеблока Сегодня разделили затраты в агенте Экономика по образцу модели НАСОСЫ, добавили расчёт ROI и построили первый. . .
23. что сделано за последнее время.
anaschu 17.06.2026
• Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru