![]() |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
![]() |
Dogmatic |
![]()
Сообщение
#1
|
![]() Группа: Пользователи Сообщений: 9 Репутация: ![]() ![]() ![]() |
Проверка выпуклости многоугольника.
Даны координаты n точек (x1, y1), (x2, y2), ..., (xn, yn). Выясните, являются ли они (именно в заданном порядке) вершинами выпуклого многоугольника. достаточно просто функции. Решение выложу через 2(ну может 3) дня. 30.11 -------------------- "Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
|
![]() ![]() |
Dogmatic |
![]()
Сообщение
#2
|
![]() Группа: Пользователи Сообщений: 9 Репутация: ![]() ![]() ![]() |
Построение выпуклой оболочки.
На плоскости задано несколько точек. Перечислить вершины многоугольника, являющегося их выпуклой оболочкой, в порядке следования по периметру. Вообщем обратная задача. (по-моему по-сложнее) -------------------- "Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
|
Dogmatic |
![]()
Сообщение
#3
|
![]() Группа: Пользователи Сообщений: 9 Репутация: ![]() ![]() ![]() |
Хм, вот ответ на 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-ю ??? -------------------- "Разум есть оружее лени, лишь умный человек может позволить себе быть ленивым" (Я)
|
![]() ![]() |
![]() |
Текстовая версия | 20.07.2025 10:44 |