P16788 [Lanqiao Cup 2026 National A] Independent Triangles

There are $N$ distinct integer points on a 2D plane. Each point has a $y$-coordinate of either $1$ or $-1$. Xiaolan wants to connect these points to form as many triangles as possible. Each triangle must satisfy: - The three vertices must not be collinear. - Different triangles must not share vertices. Since when a point is used as a vertex of a triangle, it will be connected to the other two vertices, each point can be an endpoint of at most two line segments. Now, under the condition that the number of triangles is maximized, find the maximum possible sum of the areas of all triangles. The problem guarantees that this maximum area sum is an integer.

The first line contains an integer $N$. The next $N$ lines each contain two integers $x_i, y_i$, representing the coordinates of a point. It is guaranteed that $|y_i| = 1$, and no two points coincide.

Output one line containing two integers: the maximum number of triangles that can be formed, and the maximum possible sum of areas under that maximum number of triangles.

### Sample Explanation 1 The three points can form one triangle. Using the two upper points as the base, the base length is $2$, and the distance between the upper and lower lines is $2$, so the area is $\frac{1}{2} \times 2 \times 2 = 2$. ### Sample Explanation 2 The $x$-coordinates of the points with $y = 1$ are $0, 1, 3$, and the $x$-coordinates of the points with $y = -1$ are $1, 2, 4$. At most $2$ triangles without shared vertices can be formed. One optimal plan is: use the two upper points with $x = 0$ and $3$ as the base of one triangle, with area $3$; use the two lower points with $x = 1$ and $4$ as the base of another triangle, also with area $3$. The total area is $6$. ### Constraints and Notes for Evaluation For $30\%$ of the testdata, $1 \le N \le 300$. For all testdata, $1 \le N \le 2 \times 10^5$, and $|x_i| \le 10^9$. Translated by ChatGPT 5