Data 1, 2, 3, 4

Data 1, 2, 4, 3

Data 1, 3, 2, 4

Data 1, 2, 4, 3

Data 1, 4, 2, 3

Data 1, 4, 3, 2

tchks: 'координаты точек

Data 0, 0

Data 0, 3

Data 4, 0

Data 4, 3

Результаты выполнения на ЭВМ приведенной программы:

координаты точек:

0 0

4 0

4 3

 

маршруты: длина:

1 2 3 4 16

1 2 4 3 14

1 3 2 4 18

1 2 4 3 14

1 4 2 3 18

1 4 3 2 16

максимальный маршрут:

1 3 2 4

длина =18

минимальный маршрут:

1 2 4 3

длина = 14

 

Четвертую задачу можно отнести к геометрическим задачам, ре­шение которых опирается на некоторые геометрические законы и свойства. Эта задача наиболее сложная среди рассмотренных задач из-за необходимости привлечения определенных математических знаний для организации ее решения.

Задача 4. «Ломаная».

Найти все точки самопересечения разноцветной замкнутой линии, заданной на плоскости координатами своих вершин в порядке обхода ломаной. Данные о ломаной представляются таблицей:

х	у

 

Особенность этой задачи - большое число частных случаев, свя­занных с возможным вырождением или наложением отрезков ло­манной линии. Именно эти ситуации и составляют содержание те­стов, на которых большинство программ дают неправильные резуль­таты.

Приведем проверочные тесты:

Tecт₁. (Основной случай)

 

 

Правильные результаты:

точки пересечения

0.5 0.5

 

Тест ₂. (Основной случай)

 

 

Правильные результаты:

точки пересечения:

отсутствуют

 

Тест₃. (Наложение вершины)

 

0.5

 

Правильные результаты:

точки пересечения

0.5 0

 

Тест₄. (Наложение ребра)

 

0.2
0.8

 

Правильные результаты:

отрезок пересечения:

[0.2, 0] - [0.8, 0]

Для систематического конструирования алгоритмов и программы необходима разработка сценария диалога и описание метода решения поставленной геометрической задачи.

Сценарий

точек: < n>

координаты точек:

< k>: < x> < у>

……..

точки пересечения:

отрезок: < k> - < k+l> *

отрезок: < 1> - < 1+1>

точка: < х> < у>

………

отсутствуют

 

Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х₁, у₁) - (x₂, у₂) и (х₃, y₃) - (х₄, y₄) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:

(y₂ – y₁)× (x – x₁) - (x₂ – x₁)× (y – у₁) = 0;

(у₄ – у₃)× (x – x₃) - (x₄ – x₃)× (у – y₃) = 0.

 

Решение этих уравнений может быть проведено вычислением определителей D, D_x, D_y приведенной системы уравнений:

 

(у₂ – у₁)× х - (х₂ – х₁)× у = (у₂ – y₁)× х₁ - (x₂ – x₁)× y₁;

(у₄ – y₃)× х - (х₄ – х₃) × у = (у₄ – у₃)× х₃- (x₄ – x₃)× y₃,

 

для которой будет справедлив следующий набор расчетных формул:

 

х = D_x/D;

у = D_y/D;

D = (у₂ - у₁)× (х₄ - x₃) - (x₂ - x₁)× (y₄ - y₃);

D_x = [(y₂ - y_l)× x_l - (х₂ – x₁)× y₁] - (x₄ – х₃) - (x₂ – x₁)× [(y₄ – y₃)× x₃ - (х₄ – х₃)× y₃];

D_y = (у₂ - у₁)× [(у₄ – у₃)× х₃ - (x₄ - x₃)× у₃] - [(у₂ – y₁)× x₁ - (х₂ – x₁)× y₁]× (y₄ – y₃).

 

Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтерна­тивного отрезка и сравнением значений этих выражений. А именно отрезок [(х₃, у₃) - (х₄, у₄)] пересекает линию, проходящую через отрезок [(x₁, y₁) - (х₂, у₂)], если эти выражения имеют разные знаки:

 

(у₂ - у₁)× (х₃ – x₁) - (х₂ – х₁)× (y₃ – у₁) ´ (у₂ - у₁)× (х₄ – x₁) - (х₂ – x₁)× (y₄ – y₁) £ 0.

 

Соответственно, отрезок [(х₁, у₁) - (х₂, у₂)] пересекает линию, проходящую через отрезок [(х₃, у₃) - (х₄, у₄)], если аналогичные выражения имеют разные знаки:

 

(у₄ – у₃)× (х₁ – х₃) - (х₄ – х₃)× (у₁ – у₃)´ (у₄ – у₃)× (х₂ – х₃) - (х₄ – х₃)× (у₂ – у₃) £ 0.

 

И наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказываются на одной прямой линии. В этом случае отрезки либо вообще не пересекаются, либо имеют общую часть, которую можно определить из взаимного расположения отрезков на прямой.

В последнем случае общая часть отрезков находится из взаимо­расположения отрезков [(х₁, у₁) - (х₂, у₂)] и [(х₃, у₃) - (х₄, у₄)] на прямой. В данной ситуации взаиморасположение вершин отрезков можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х₁, у₁) - (х₂, у₂)] по следующим фор­мулам:

 

d₁ = 0;

d₂ = (х₂ – х₁)× (х₂ – х₁) + (у₂ – у₁)× (у₂ - 1);

d₃ = (х₃ – х₁)× (x₂ – х₁) + (у₃ - у₁)× (у₂ - 1);

d₄ = (х₄ – х₁)× (х₂ – х₁) + (у₄ – y₁)× (y₂ - 1).

 

Если d₂ < min (d₃, d₄) или max (d₃, d₄) < 0, то отрезки не пересе­каются. В противном случае необходимо выделить и отбросить две крайние точки, и тогда оставшиеся две точки зададут общую часть этих отрезков.

Опираясь на эти математические факты можно приступить к составлению алгоритмов и программы. Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное число точек устанавливается при вводе исходных данных из перечня операторов data, записанных в конце текста программы.

¢ самопересечение ломаной

nt = 200