問題一覧 > 通常問題

No.947 ABC包囲網

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : maimai / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
2 ProblemId : 3612 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-11 21:16:58

note

Advent Calender Contest Advent Calendar 2019 の 10 日目です。

問題文

ユークリッド平面上に存在する $n$ 個の点 $P_1 \ldots P_n$ が与えられます。
$n$ 個の点から 3 つ選ぶ組合せのうち、その 3 点から構成される三角形の内部(辺上を除く)に点 $(0, 0)$ が含まれるものは何通りありますか？

入力

$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$
すべて整数。
点座標は重複しない。
(0, 0) は入力に含まれない。(01:40追記)

出力

最後に改行してください。

サンプル

サンプル1
入力
4
-1 -1
2 1
1 2
-1 2
出力
2

上図は、入力と (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

辺上は内部とみなしません

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