/
実行時間制限: 1 sec / メモリ制限: 256 MiB
配点 : 100 点
問題文
K 理事長は国際情報オリンピック日本選手団を応援するポスターを 3 枚デザインしている.ポスターにはそれぞれ J,O,I の文字を 1 文字ずつ盛り込む予定である.早速文字 J と文字 I のポスターを完成させた K 理事長は,残る文字 O のポスターをオーストラリアの星空を背景にデザインしようと考えた.
ポスターは幅 W,高さ H の長方形で,左下隅の座標が (0, 0),右上隅の座標が (W, H) である.ポスター上には N 個の星が印刷されている.i 番目の星 S_{i} (1 \leqq i \leqq N) のポスター上での座標は (X_{i}, Y_{i}) であり,どの 2 つの星も同じ座標にない.
K 理事長は文字 O のデザインを作成するにあたり,以下のように考えた.N 個の星のうち,異なる 4 つの星を選びそれぞれ A, B,C, D とする.A を中心とし B を通る円を円 O_{1},C を中心とし D を通る円を円 O_{2} とする.2 つの円 O_{1}, O_{2} が以下の両方の条件を満たすとき,4 つの星 A, B,C, D は K 理事長のデザインの候補となる.
- 円 O_{1} が円 O_{2} を内部に含む.すなわち,円 O_{2} の内部または円周上の任意の点が円 O_{1} の内部 (円周上は除く) にある.
- どちらの円もポスターの長方形領域からはみ出さない.すなわち,円の内部または円周上の任意の点 (X, Y) について,0 \leqq X \leqq W かつ 0 \leqq Y \leqq H を満たす.
K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方は何通りあるだろうか.
課題
ポスターの大きさと星の情報が与えられたとき,K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方が何通り存在するかを求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には整数 N, W, H が空白を区切りとして書かれており,ポスター上に印刷された星の数と,ポスターの幅と高さをそれぞれ表す.
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には 2 つの整数 X_{i}, Y_{i} (0 \leqq X_{i} \leqq W かつ 0 \leqq Y_{i} \leqq H) が空白を区切りとして書かれており,星 S_{i} のポスター上での座標を表す.
出力
標準出力に,K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方が何通り存在するかを表す整数を 1 行で出力せよ.
制約
すべての入力データは以下の条件を満たす.
- 4 \leqq N \leqq 50.
- 1 \leqq W \leqq 1\,000.
- 1 \leqq H \leqq 1\,000.
- 0 \leqq X_{i} \leqq W.
- 0 \leqq Y_{i} \leqq H.
- どの 2 つの星も同じ座標にない.
小課題
小課題 1 [80 点]
- 4 つの星 A, B,C, D をどのように選んでも,円 O_{1} と円 O_{2} は接しない.
小課題 2 [20 点]
追加の制限はない.
入出力例
入力例 1
7 20 15 9 5 13 9 15 13 7 4 6 8 14 7 16 7
出力例 1
3
この入力例は以下の図に対応している.星 S_{i} を点 i で表す.

この図において K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方は 3 通り存在する.
それぞれの場合における円 O_1, O_2 を以下の図で示す.


3 つ目の図において,円 O_{1} と円 O_{2} は接していないことに注意せよ.
入力例 2
15 20 30 11 8 14 25 3 20 1 27 2 16 12 8 0 4 3 10 12 11 5 9 16 3 2 13 4 24 18 3 12 28
出力例 2
12