No.947 ABC包囲網
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 :
mai
/ テスター :
nmnmnmnmnmnmnm
タグ : / 解いたユーザー数 41
作問者 :

問題文最終更新日: 2025-02-10 00:15:01
note
Advent Calender Contest Advent Calendar 2019 の 10 日目です。
問題文
ユークリッド平面上に存在する 個の点 が与えられます。
個の点から 3 つ選ぶ組合せのうち、その 3 点から構成される三角形の内部(辺上を除く)に点 が含まれるものは何通りありますか?
入力
すべて整数。
点座標は重複しない。
(0, 0) は入力に含まれない。(01:40追記)
出力
最後に改行してください。
サンプル
サンプル1
入力
4 -1 -1 2 1 1 2 -1 2
出力
2
.svg.png)
上図は、入力と (0,0)の点をプロットしたものです。横軸が切れていますが…
(-1, -1) (2, 1) (1, 2)
は O を含みます。(-1, -1) (2, 1) (-1, 2)
は O を含みます。(-1, -1) (1, 2) (-1, 2)
は O を含みません。(2, 1) (1, 2) (-1, 2)
は O を含みません。
サンプル2
入力
4 -1 -1 1 1 -1 1 1 -1
出力
0
.svg.png)
辺上は内部とみなしません
サンプル3
入力
8 1000000000 1000000000 1000000000 999999999 999999999 1000000000 999999999 999999999 -1000000000 -1000000000 -1000000000 -999999999 -999999999 -1000000000 -999999999 -999999999
出力
4
△
お役立ち情報
手元に方眼用紙がありませんか?
csacademy geometry_widget が便利です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。