問題一覧 > 通常問題

No.947 ABC Encirclement

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : mai / テスター : nmnmnmnmnmnmnm
お気に入りにしたユーザー ProblemId : 3612 / 自分の提出
問題文最終更新日: 2025-02-10 00:15:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

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

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

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もしくは右上の雲マークをクリックしてアカウントを作成してください。