TUZ_2-16 Удаление правильных прямых углов в двумерной сетке
Для данного набора точек в двумерной сетке под «углом» понимаются три точки в форме (x, y), (x, y + h) и (x + h, y)
для некоторого значения h > 0, представляющие острие угла с двумя крыльями.
Ваша задача: написать функцию
Cut_corners(points) , которая принимает список точек,
и возвращает минимальное количество точек, которые необходимо удалить из списка,
чтобы исключить все правильные прямые углы.
В табл. 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 |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3
3 8
8 3
|
1
|