Triangles

Time limit2sMemory limit1024 MB

Summary

Count the triangles formed by mutant triples that strictly contain the point Cerebro, given n points up to 10^5 and coordinates up to 10^9.

Level: Medium7 of 10
Topics: Geometry, Sorting, Two pointers, Math
Solved: No attempts yet

Problem

While designing Cerebro, a computer that can locate any mutant on Earth, Xavier ran into the following problem. Searching for all mutants at once is extremely hard. Each mutant has its own power, and each mutant creates some interference that gets in the way of the search. If the Earth is treated as a flat plane (a reasonable assumption when searching a limited area), then each mutant and Cerebro can be represented as points on the plane. Every triple of mutants such that Cerebro lies strictly inside the triangle formed by those three mutants adds one unit of interference. If Cerebro is outside the triangle or on its boundary, no interference is added. The total interference is the sum over all triples of mutants. Help Charles find this number.

Input

The first line contains one integer $n$ ( $3 \le n \le 10^5$ ), the number of mutants.

The second line contains two integers $x, y$ ( $-10^9 \le x, y \le 10^9$ ), the coordinates of Cerebro.

The next $n$ lines each contain two integers $x_i, y_i$ ( $-10^9 \le x_i, y_i \le 10^9$ ), the coordinates of the mutants.

The coordinates of all points (both the mutants and Cerebro) are pairwise distinct.

Output

Print one line containing the total interference.

Examples2

Example 1
Input
```
6
0 0
1 1
-1 1
1 -1
-1 -1
2 0
0 2
```
Expected output
```
3
```
Example 2
Input
```
3
0 0
0 1
-1 -1
1 -1
```
Expected output
```
1
```