4 - JOIポスター (JOI Poster) 解説 /

実行時間制限: 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

出典

JOI 2012/2013 春季トレーニング合宿 Contest Day1