K 理事长正在设计 3 张海报,以支持国际信息学奥林匹克(IOI)日本代表团。海报上计划分别印有字母 "J"、"O"、"I"。K 理事长已经迅速完成了字母 "J" 和 "I" 的海报,现在他打算以澳大利亚的星空为背景来设计剩下的字母 "O" 的海报。
海报是一个宽为 $W$、高为 $H$ 的矩形,左下角坐标为 $(0, 0)$,右上角坐标为 $(W, H)$。海报上印有 $N$ 颗星星。第 $i$ 颗星星 $S_i$ ($1 \le i \le N$) 在海报上的坐标为 $(X_i, Y_i)$,任意两颗星星的坐标均不相同。
K 理事长在设计字母 "O" 时,提出了以下想法:从 $N$ 颗星星中选择 4 颗不同的星星,分别记为 $A, B, C, D$。以 $A$ 为圆心且经过 $B$ 的圆记为圆 $O_1$,以 $C$ 为圆心且经过 $D$ 的圆记为圆 $O_2$。如果这两个圆 $O_1, O_2$ 同时满足以下两个条件,则这 4 颗星星 $A, B, C, D$ 的组合就是 K 理事长设计方案的一个候选:
- 圆 $O_1$ 内部包含圆 $O_2$。也就是说,圆 $O_2$ 的内部或圆周上的任意一点都在圆 $O_1$ 的内部(不包括圆周上)。
- 两个圆都不超出海报的矩形区域。也就是说,对于圆内部或圆周上的任意一点 $(X, Y)$,都满足 $0 \le X \le W$ 且 $0 \le Y \le H$。
问:共有多少种选择 4 颗星星 $A, B, C, D$ 的方法,使得它们能成为 K 理事长设计方案的候选?
课题
给定海报的大小和星星的信息,编写一个程序,求出有多少种选择 4 颗星星 $A, B, C, D$ 的方法,使其成为 K 理事长设计方案 of 候选。
输入格式
从标准输入中读取以下内容:
- 第一行包含三个空格分隔的整数 $N, W, H$,分别表示海报上印有的星星数量、海报的宽度和高度。
- 接下来的 $N$ 行中,第 $i$ 行($1 \le i \le N$)包含两个空格分隔的整数 $X_i, Y_i$($0 \le X_i \le W$ 且 $0 \le Y_i \le H$),表示星星 $S_i$ 在海报上的坐标。
输出格式
向标准输出输出一行,包含一个整数,表示满足 K 理事长设计方案候选条件的 4 颗星星 $A, B, C, D$ 的选择方法总数。
数据范围
所有输入数据均满足以下条件:
- $4 \le N \le 50$
- $1 \le W \le 1000$
- $1 \le H \le 1000$
- $0 \le X_i \le W$
- $0 \le Y_i \le H$
- 任意两颗星星的坐标均不相同。
子任务
官方测试数据包含 10 个独立的子任务。
子任务 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$ 如下图所示:
请注意,在第三幅图中,圆 $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