P2782 Friendly Cities

There is an east-west river with straight north and south banks. On each bank, there are $N$ cities at distinct positions. Each city on the north bank has exactly one friendly city on the south bank, and different cities have different friendly cities. Each pair of friendly cities applies to build a straight shipping lane across the river connecting the two cities. However, due to heavy fog on the river, the government decides to avoid any two lanes crossing to prevent accidents. Write a program to approve and reject some applications so that, while ensuring no two lanes cross, the number of approved applications is maximized.

The first line contains an integer $N$, the number of cities. From the second line to the $(N+1)$-th line, each line contains two integers separated by a space, representing the coordinates of a pair of friendly cities on the south and north banks, respectively.

Output a single line with one integer, the maximum number of applications the government can approve.

Constraints - For $50\%$ of the testdata, $1 \leq N \leq 5000$, $0 \leq x_i \leq 10000$. - For $100\%$ of the testdata, $1 \leq N \leq 2 \times 10^5$, $0 \leq x_i \leq 10^6$. Translated by ChatGPT 5