P6149 [USACO20FEB] Triangles S

Farmer John wants to build a triangular pasture for his cows. There are $N$ ($3 \leq N \leq 10^5$) fence posts located at distinct points $(X_1, Y_1) \ldots (X_N, Y_N)$ on the 2D plane of the farm. He may choose any three points to form a triangular pasture, as long as one side of the triangle is parallel to the $x$-axis and another side is parallel to the $y$-axis. What is the sum of the areas of all possible pastures that FJ can form?

The first line contains $N$. The next $N$ lines each contain two integers $X_i$ and $Y_i$, both in the range $-10^4 \ldots 10^4$, describing the position of a fence post.

Since the sum of areas may not be an integer and may be very large, output the remainder of **twice** the sum of areas modulo $10^9 + 7$.

#### Sample Explanation: The fence posts $(0,0)$, $(1,0)$, and $(1,2)$ form a triangle with area $1$, and the fence posts $(0,0)$, $(1,0)$, and $(0,1)$ form a triangle with area $0.5$. Therefore, the answer is $2 \times (1 + 0.5) = 3$. #### Subtasks: - Test case $2$ satisfies $N = 200$. - Test cases $3$-$4$ satisfy $N \leq 5000$. - Test cases $5$-$10$ have no additional constraints. Translated by ChatGPT 5