P2772 Finding Maximal Points on the Plane

On a plane, for two points $(x,y)$ and $(a,b)$, we say that $(x,y)$ dominates $(a,b)$ if $x\ge a$ and $y\ge b$. Geometrically, this means that $(a,b)$ lies in the unbounded region whose upper-right corner is $(x,y)$. Given a set of $n$ points, there exist some points that are not dominated by any other point in the set; these points are called maximal points. Write a program to find all maximal points and output their coordinates in increasing order of the $x$-coordinate.

The input consists of two lines. The first line is a positive integer $n$, the number of points. The second line contains $n$ points’ coordinates. All coordinates are integers. No two points in the input share the same coordinates.

Output all maximal points in increasing order of the $x$-coordinate. The output format is: $(x1,y1),(x2,y2),\cdots,(xk,yk)$. Note: Each point is separated by `,`, and there is no `,` after the last point. Missing or extra output will be judged incorrect.

For $50\%$ of the testdata: $1\le n\le 100$; $0\le x,y\le 10^5$. For $100\%$ of the testdata: $1\le n\le 5\times 10^5$; $0\le x,y\le 10^5$. Translated by ChatGPT 5