問題一覧 > 通常問題

No.1497 Triangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 : tatyamtatyam
3 ProblemId : 6408 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-04 00:15:55

問題文

$2$ 次元平面に $1, 2, \dots, N$ の番号がついた $N$ 個の点があります。点 $i$ の座標は $(x_i, y_i)$ で、$N$ 個の点の座標は相異なります。
すぬけくんは、平面上に面積が正の三角形を $1$ つ描き、その内部と境界上にある点を全て赤く塗りました。
赤く塗られた頂点の集合として考えられるものは何通りあるでしょうか?

入力

$N$
$x_1$ $x_2$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$
  • 入力は全て整数
  • $1 ≤ N ≤ 22$
  • $0 ≤ x_i, y_i ≤ 10^3$
  • $i ≠ j$ ならば $(x_i, y_i) ≠ (x_j, y_j)$

出力

答えを整数で出力せよ。

サンプル

サンプル1
入力
3
0 0
1 2
2 0
出力
8

例えば、すぬけくんが以下のように三角形を描くと、三角形の内部にある頂点 $1, 3$ を赤く塗ることができます。

サンプル2
入力
4
0 0
1 2
2 0
1 1
出力
15

頂点 $1, 2, 3$ を赤く塗り、頂点 $4$ を赤く塗らないような三角形の描き方はありません。

サンプル3
入力
1
0 0
出力
2
サンプル4
入力
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
出力
2092
ヒント
入力
7
100 48
50 49
1 50
0 100
1 150
50 151
100 152
出力
127

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