P3699 [CQOI2017] Xiao Q's Scratch Paper

Q is a programmer. As we all know, programmers often need scratch paper when writing programs. Xiao Q now needs a sheet of scratch paper to draw a figure, but there is only one sheet on the desk, and it has already been used many times. We can regard the scratch paper as a 2D plane, and Xiao Q has even set up a Cartesian coordinate system on it. Each previously used region can be approximated as a triangle on the plane. The interior and boundary of such a triangular region cannot be used again. Also, previously used regions do not overlap. Xiao Q has already marked several key points on the scratch paper, all lying in unused regions. He wants to connect as many pairs of these key points as possible with straight segments. A segment connecting two key points may pass through an already used triangular region, which is not allowed. Therefore, Xiao Q wants to know how many pairs of key points can be connected by a straight segment without intersecting the interior or boundary of any used triangular region. For convenience, it is guaranteed that no three key points are collinear.

The first line contains two integers V, T, denoting the number of key points and the number of triangular regions on the scratch paper. The next V lines each contain two integers x, y, representing the coordinates of a key point $(x, y)$. Then T lines follow. Each line contains six integers $x_1, y_1, x_2, y_2, x_3, y_3$, indicating that the three vertices of a triangular region are $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$, and the area of the triangle is greater than $0$.

Output one line with a single integer, the number of pairs of key points that can be connected by a straight segment without intersecting any used triangular region.

[Explanation for Sample 1] The entire scratch paper is unused, so any two key points can be connected. [Explanation for Sample 2] As shown in the figure, the segment between any two key points is blocked.  Constraints For 100% of the test points, all coordinates are integers and satisfy $0 \le \text{coordinate} \le 10^8$. ```cpp NO 1 2 3 4 5 6 7 8 9 10 V 10 20 50 100 200 400 600 1000 1000 1000 T 10 20 50 100 200 400 600 1000 1000 1000 ``` Translated by ChatGPT 5