問題一覧 > 通常問題

No.1497 Triangle

レベル : / AI推定難易度 : 2750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : tatyam
お気に入りにしたユーザー ProblemId : 6408 / 自分の提出
問題文最終更新日: 2026-10-25 12:20:57
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
tatyamさん問題 (順位表) の他の問題:

Problem Statement

There are $N$ points numbered $1, 2, \dots, N$ on a $2$-dimensional plane. The coordinates of point $i$ are $(x_i, y_i)$, and the coordinates of the $N$ points are pairwise distinct.
Snuke drew $1$ triangle with positive area on the plane and painted red all the points inside it or on its boundary.
How many possible sets of vertices painted red are there?

Input

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$
  • All inputs are integers.
  • $1 ≤ N ≤ 22$
  • $0 ≤ x_i, y_i ≤ 10^3$
  • If $i ≠ j$, then $(x_i, y_i) ≠ (x_j, y_j)$.

Output

Output the answer as an integer.

Sample

Sample 1
Input
3
0 0
1 2
2 0
Output
8

For example, if Snuke draws a triangle as shown below, vertices $1, 3$, which are inside the triangle, can be painted red.

Sample 2
Input
4
0 0
1 2
2 0
1 1
Output
15

There is no way to draw a triangle such that vertices $1, 2, 3$ are painted red and vertex $4$ is not painted red.

Sample 3
Input
1
0 0
Output
2
Sample 4
Input
15
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
Output
2092
Hint
Input
7
100 48
50 49
1 50
0 100
1 150
50 151
100 152
Output
127

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。