시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB108272436.923%

문제

K 理事長は国際情報オリンピック日本選手団を応援するポスターを 3 枚デザインしている.ポスターに はそれぞれ J,O,I の文字を 1 文字ずつ盛り込む予定である.早速文字 J と文字 I のポスターを完成させた K 理事長は,残る文字 O のポスターをオーストラリアの星空を背景にデザインしようと考えた.

ポスターは幅 W,高さ H の長方形で,左下隅の座標が (0, 0),右上隅の座標が (W, H) である.ポスター 上には N 個の星が印刷されている.i 番目の星 Si (1 ≤ i ≤ N) のポスター上での座標は (Xi, Yi) であり,どの 2 つの星も同じ座標にない.

K 理事長は文字 O のデザインを作成するにあたり,以下のように考えた.N 個の星のうち,異なる 4 つ の星を選びそれぞれ A, B, C, D とする.A を中心とし B を通る円を円 O1,C を中心とし D を通る円を円 O2 とする.2 つの円 O1, O2 が以下の両方の条件を満たすとき,4 つの星 A, B, C, D は K 理事長のデザイン の候補となる.

  • 円 O1 が円 O2 を内部に含む.すなわち,円 O2 の内部または円周上の任意の点が円 O1 の内部 (円周 上は除く) にある.
  • どちらの円もポスターの長方形領域からはみ出さない.すなわち,円の内部または円周上の任意の点 (X, Y) について,0 ≤ X ≤ W かつ 0 ≤ Y ≤ H を満たす.

K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方は何通りあるだろうか.

ポスターの大きさと星の情報が与えられたとき,K理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方が何通り存在するかを求めるプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N, W, H が空白を区切りとして書かれており,ポスター上に印刷された星の数と,ポ スターの幅と高さをそれぞれ表す.
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には 2 つの整数 Xi, Yi (0 ≤ Xi ≤ W かつ 0 ≤ Yi ≤ H) が空白を区 切りとして書かれており,星 Si のポスター上での座標を表す.

출력

標準出力に,K 理事長のデザインの候補となるような 4 つの星 A, B, C, D の選び方が何通り存在するか を表す整数を 1 行で出力せよ.

제한

  • 4 ≤ N ≤ 50.
  • 1 ≤ W ≤ 1 000.
  • 1 ≤ H ≤ 1 000.
  • 0 ≤ Xi ≤ W.
  • 0 ≤ Yi ≤ H.
  • どの 2 つの星も同じ座標にない.

예제 입력 1

7 20 15
9 5
13 9
15 13
7 4
6 8
14 7
16 7

예제 출력 1

3

この入力例は以下の図に対応している.星 Si を点 i で表す.

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

3 つ目の図において,円 O1 と円 O2 は接していないことに注意せよ.

예제 입력 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

출처

Camp > JOI Spring Training Camp > JOI 2012/2013 Spring Training Camp 1-4번

  • 문제의 오타를 찾은 사람: xiaowuc1

채점 및 기타 정보

  • 예제는 채점하지 않는다.