IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Ответ на 1-ю уже есть!!!Выпуклость многоугольника.
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 9

Репутация: -  0  +


Проверка выпуклости многоугольника.
Даны координаты n точек (x1, y1), (x2, y2), ..., (xn, yn). Выясните, являются ли они (именно в заданном порядке) вершинами выпуклого многоугольника.

достаточно просто функции.

Решение выложу через 2(ну может 3) дня. 30.11


--------------------
"Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 9

Репутация: -  0  +


Построение выпуклой оболочки.  
На плоскости задано несколько точек. Перечислить вершины многоугольника, являющегося их выпуклой оболочкой, в порядке следования по периметру.
Вообщем обратная задача. (по-моему по-сложнее)


--------------------
"Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 9

Репутация: -  0  +


Хм, вот ответ на 1-ю задачу:

type point = record
x, y: integer;
end;

(*
* Эта функция вычисляет ориентацию треугольника.
* Разные ориентации дают ответы 1 и -1, ответ 0
* означает, что треугольник вырожден.
*)
function orientation(A, B, C: point): integer;
var signedDoubledArea: integer;
begin
signedDoubledArea := A.x * B.y - A.y * B.x +
B.x * C.y - B.y * C.x +
C.x * A.y - C.y * A.x;

if (signedDoubledArea = 0) then
orientation := 0
else if (signedDoubledArea > 0) then
orientation := 1
else
orientation := -1;
end;

(*
* Проверяем условие локальной выпуклости.
*)
function isLocalConvex(var p: array of point): boolean;
var o, i: integer;
begin
o := orientation(p[0], p[1], p[2]);
if (o = 0) then
isLocalConvex := false
else
begin
isLocalConvex := true;
for i := 1 to high(p) do
if (o <> orientation(p[i],
p[(i + 1) mod (high(p) + 1)],
p[(i + 2) mod (high(p) + 1)])) then
begin
isLocalConvex := false;
break;
end;
end;
end;

(*
* Проверяем условие глобальной выпуклости.
*)
function isGlobalConvex(var p: array of point): boolean;
var counter, i: integer;
begin
(*
* Это счетчик количества перемен направления движения с "вверх" на "вниз".
*)
counter := 0;
isGlobalConvex := true;

for i := 0 to high(p) do
if ((p[i].y <= p[(i + 1) mod (high(p) + 1)].y) and
(p[(i + 1) mod (high(p) + 1)].y > p[(i + 2) mod (high(p) + 1)].y)) then
begin
inc(counter);
if (counter = 2) then
begin
isGlobalConvex := false;
break;
end;
end;
end;

(*
* Проверка того, что данная ломаная -- выпуклый многоугольник,
* состоит в последовательной проверке условий локальной и глобальной
* выпуклости.
*)
function isConvex(var p: array of point): boolean;
begin
isConvex := isLocalConvex(p) and isGlobalConvex(p);
end;


Может это поможет кому-нибудь решить 2-ю ???


--------------------
"Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 25.11.2020 15:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name