TUZ_6-05 Подсчет количества максимальных слоев на двумерной плоскости
6.5. Подсчет количества максимальных слоев на двумерной плоскости
Точка на двумерной плоскости с координатами (x1, y1) доминирует над точкой (x2, y2), если x1 > x2 и y1 > y2.
Если над точкой не доминирует никакая другая точка, то она считается максимальной, причем на двумерной плоскости
может иметься произвольное количество точек, образующих максимальный слой.
Цель этого задания: подсчитать количество максимальных слоев.
Например, пусть дан список точек points = [(1, 5), (3, 10), (2, 1), (9, 2)]
и для него нужно подсчитать количество максимальных слоев.
- Входные данные просматриваются слева направо, точка (1, 5) не является максимальной,
потому что над ней доминирует точка (3, 10), т. е. 3 > 1 и 10 > 5.
- Следующая рассматриваемая точка – точка (3, 10), это максимальная точка,
потому что над ней не доминирует никакая другая точка:
- для пары (1, 5) и (3, 10) 1 не больше 3 и 5 не больше 10,
- для пары (2, 1) и (3, 10) 2 не больше 3 и 1 не больше 10,
- и для пары (9, 2) и (3, 10) 9 больше 3, но 2 не больше 10.
- Следующей рассматривается точка (2, 1), и она не является максимальной,
потому что над ней доминирует точка (3, 10).
- Следующая точка – (9, 2) – является максимальной, потому что над ней, как и над (3, 10),
не доминирует никакая другая точка.
Следовательно, в списке points = [(1, 5), (3, 10), (2, 1), (9, 2)] есть два максимальных слоя,
один из них образован точкой (10, 3), а другой – точкой (9, 2).
Ваша задача: написать функцию, которая принимает список точек и возвращает количество максимальных слоев.
В табл. 6.5 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 6.5. Некоторые ожидаемые результаты для задачи подсчета количества максимальных слоев на двумерной плоскости |
| Points |
Ожидаемый результат |
| (7, 1), (6, 9) |
1 |
| (11, 4), (1, 1), (11, 1) |
2 |
| (1, 5), (3, 10), (2, 1), (9, 2) |
2 |
| (796, 1024), (11, 13), (19, 221), (700, 3) |
3 |