問題一覧 > 通常問題

No.947 ABC包囲網

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : mai / テスター : nmnmnmnmnmnmnm
2 ProblemId : 3612 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-10 00:15:01

note

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

問題文

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

入力

nn
Px1 Py1{P_x}_1\ {P_y}_1
\ldots
Pxn Pyn{P_x}_n\ {P_y}_n

3n4×1033 \le n \le 4\times 10^3
109Pxi,Pyi109-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もしくは右上の雲マークをクリックしてアカウントを作成してください。