Олимпиадные задачи по информатике - часть 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]
Для систематического конструирования алгоритмов и программы необходима разработка сценария диалога и описание метода решения поставленной геометрической задачи.
Сценарий
<k>: <x> <у>
точки пересечения:
отрезок: <1> - <1+1>
точка: <х> <у>
………
Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений: