No.1497 Triangle
レベル :
/ AI推定難易度 : 2750
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 :
tatyam
タグ : / 解いたユーザー数 4
作問者 :
tatyam
問題文最終更新日: 2026-10-25 12:20:57
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。