The James Webb Space Telescope (JWST) has been launched to the Earth's orbit on 25 Dec 2021. The telescope allows Lester, a physicist, to better examine the stars in the universe.
The Pillars of Creation, NASA
Now Lester would like to analyze a $N \times M$ rectangular grid of an image taken by JWST. The bottom left corner is $(0, 0)$, and the bottom right corner is $(0, M)$. In the grid, there are $S$ stars. He proceeds to find the brightest star at $(x, y)$. A bright constellation is defined as a triangle formed with the brightest star and two other stars as its vertices. Please help Lester to count the number of distinct bright constellations.
Input
The first line consists of $N, M, S$. The following $S$ lines each contains $x_i, y_i$, the coordinate of the $i$-th star. The last line of the input consists of $x, y$, the coordinate of the brightest star.
Output
Output 1 integer, the number of distinct bright constellations.
Constraints
For all subtasks: $1 \le N, M \le 10^{18}$, $1 \le S \le \min(10^6, (N+1) \times (M+1))$, $0 \le x_i \le N$, $0 \le y_i \le M$.
Subtask 1(10%): $N, M, S \le 10$
Subtask 2(30%): $N, M, S \le 1000$
Subtask 3(60%): No additional constraints
Sample Test Cases
Input | Output | |
---|---|---|
2 2 5 0 0 2 2 0 2 2 0 1 1 1 1 |
4 | |
4 4 5 0 0 1 1 2 2 3 3 4 4 2 2 |
0 |
Scoring: Per Subtask
Authored by s17f18
Appeared in 2022 Mini Contest 3 (Pre-HKOI Junior)