TUZ_2-16 Удаление правильных прямых углов в двумерной сетке
2.16 Удаление правильных прямых углов в двумерной сетке
Для данного набора точек в двумерной сетке под «углом» понимаются три точки в форме (x, y), (x, y + h) и (x + h, y)
для некоторого значения h > 0, представляющие острие угла с двумя крыльями.
Ваша задача: написать функцию, которая принимает список точек, упорядоченных по углам, и возвращает минимальное количество точек,
которые необходимо удалить из списка, чтобы исключить все правильные прямые углы.
В табл. 2.16 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.16. Некоторые ожидаемые результаты для задачи удаления правильных прямых углов в двумерной сетке |
| Points |
Ожидаемый результат |
| (3, 3), (3, 8), (8, 3) |
1 |
| (0, 1), (4, 5), (3, 2) |
0 |
| (5, 0), (1, 3), (1, 4), (2, 0), (2, 2), (2, 3), (4, 0), (4, 0) |
2 |