No.1144 Triangles
null
hotman78Introduction
A solution in C++ has been confirmed to pass with time to spare, but the constraints may be somewhat tight. Note that the TL is 3 seconds.Problem Statement
You are given $n$ points. The $i$-th point is $P_i(x_i, y_i)$.
Find the remainder when $\displaystyle \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} 2 \times \triangle P_i P_j P_k$
is divided by $(10^9 + 7)$. Here, $\triangle ABC$ denotes the area of the triangle with vertices at points $A, B, C$. If the triangle cannot be formed, the area is taken to be $0$.
It can be shown that, under these constraints, twice the area of a triangle formed by any $3$ of the given $N$ points is an integer.
Constraints
- $3 \le n \le 2 \times 10^3$
- $-10^4 \le x_i, y_i \le 10^4$
- All input values are integers
Input
$n$ $x_1\ y_1$ $x_2\ y_2$ $\dots$ $x_n\ y_n$
Output
Print the remainder when $\displaystyle \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} 2 \times \triangle P_i P_j P_k$
is divided by $(10^9 + 7)$. Print a newline at the end.
Sample
Sample 1
Input
5 0 0 1 1 3 4 2 3 0 2
Output
25
$2 \times \triangle P_1 P_2 P_3 + 2 \times \triangle P_1 P_2 P_4 + 2 \times \triangle P_1 P_2 P_5 + 2 \times \triangle P_1 P_3 P_4 + 2 \times \triangle P_1 P_3 P_5 + 2 \times \triangle P_1 P_4 P_5 + 2 \times \triangle P_2 P_3 P_4 + 2 \times \triangle P_2 P_3 P_5 + 2 \times \triangle P_2 P_4 P_5 + 2 \times \triangle P_3 P_4 P_5 \\
1+1+2+1+6+4+1+5+3+1=25$.
Sample 2
Input
3 0 0 0 1 2 0
Output
2
Sample 3
Input
4 0 0 1 1 2 2 3 3
Output
0
Three points may lie on the same line. Although it is not the case here, two or more points may also coincide.
Sample 3
Input
10 3537 9451 9695 -7141 -3029 5335 400 5744 928 7006 -2302 -6741 -6467 -9447 3962 9075 3296 -3856 -3 7451
Output
233469265
Note that you must print the remainder when divided by $(10^9+7)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。