The point (x1, y1) on the plane is said to dominate another point (x2, y2) if it
Question:
The point (x1, y1) on the plane is said to dominate another point (x2, y2) if it lies to the right and above from it, that is, x1 > x2 and y1 > y2. A point inside the given list of points is defined to be maximal if it is not dominated by any other point in the list. Unlike in one dimension, a list of points on the two-dimensional plane can contain any number of maximal points, which then form the maximal layer for that particular list of points. For example, the points (3, 10) and (9, 2) are the maximal layer for the list of points [(1, 5), (8, 1), (3, 10), (2, 1), (9, 2)].
Given a list of points whose coordinates are guaranteed to be nonnegative, this function should compute how many times one would need to perform the operation of removing every point in the maximal layer from the list (and then compute the new maximal layer for the remaining points for the next round) for that entire list to become empty, and return that count
points Expected result
[(1, 3), (2, 2), (3, 1)]
1
[(1, 5), (3, 10), (2, 1), (9, 2)]
2
[(x, y) for x in range(10) for y in range(10)]
10
[(x, x**2) for x in range(100)]
100
[(x, x**2 % 91) for x in range(1000)]
28
[((x**3) % 891, (x**2) % 913) for x in range(10000)]
124
This is again one of those problems whose actual educational point and motivation is making this function fast enough to finish within a reasonable time even for a big list of points, by not doing too much more work than would be necessary to identify and remove the maximal points. Start by noticing that each point can potentially be dominated only by those points whose distance from the origin (0, 0) is strictly larger...