No.947 ABC Encirclement
タグ : / 解いたユーザー数 44
作問者 :
nmnmnmnmnmnmnm
note
This is day 10 of Advent Calender Contest Advent Calendar 2019.
Problem Statement
You are given $n$ points $P_1 \ldots P_n$ on the Euclidean plane.
Among the combinations of 3 points chosen from the $n$ points, how many are there such that the point $(0, 0)$ is contained in the interior (excluding the edges) of the triangle formed by those 3 points?
Input
$n$
${P_x}_1\ {P_y}_1$
$\ldots$
${P_x}_n\ {P_y}_n$
$3 \le n \le 4\times 10^3$
$-10^9 \le {P_x}_i, {P_y}_i \le 10^9$
All values are integers.
No two points have the same coordinates.
(0, 0) is not included in the input. (Added at 01:40)
Output
Print a newline at the end.
Sample
Sample 1
Input
4 -1 -1 2 1 1 2 -1 2
Output
2
.svg.png)
The figure above plots the input points and the point (0,0). The horizontal axis is cut off, though...
(-1, -1) (2, 1) (1, 2)contains O.(-1, -1) (2, 1) (-1, 2)contains O.(-1, -1) (1, 2) (-1, 2)does not contain O.(2, 1) (1, 2) (-1, 2)does not contain O.
Sample 2
Input
4 -1 -1 1 1 -1 1 1 -1
Output
0
.svg.png)
Points on an edge are not considered to be in the interior.
Sample 3
Input
8 1000000000 1000000000 1000000000 999999999 999999999 1000000000 999999999 999999999 -1000000000 -1000000000 -1000000000 -999999999 -999999999 -1000000000 -999999999 -999999999
Output
4
△
Useful Information
Don't have any graph paper at hand?
csacademy geometry_widget is handy.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。