Информатика


Олимпиадные задачи по информатике - часть 10


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

х

у

0

1

1

0

0

1

1

1

 

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

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

Tecт1.

(Основной случай)

 

0

0

0

1

1

0

1

1

 

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

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

0.5              0.5

 

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

 

0

0

0

1

1

1

1

0

 

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

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

отсутствуют

 

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

 

0

0

0

1

0.5

0

1

1

1

0

 

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

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

0.5              0

 

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

 

0

0

0

1

0.2

0

0.8

0

1

1

1

0

 

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

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

[0.2, 0] - [0.8, 0]

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

 

Сценарий

           точек: <n>

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

                                                    <k>: <x> <у> 

                                                            …….. 

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

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

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

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

            ………

     отсутствуют

 

Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:




Начало  Назад  Вперед



Книжный магазин