P2997 [USACO10NOV] Banner S

题目大意(by:曹彦臣)： 平面上有(0,0)到(n,m)的(n+1)\*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内。

Bessie 刚从国外长途旅行回来，农夫约翰想在她的牧场里竖起一个漂亮的「欢迎回家」横幅。横幅将挂在两根柱子之间的电线上，电线的长度范围是 $L_1..L_2$，其中 $1 \le L_1 \le L_2$，且 $L_1 \le L_2 \le 1,500$。 牧场的大小为 $W \times H$，其中 $1 \le W \le 1,000$，$1 \le H \le 1,000$，农夫约翰在每个整数坐标点上都安装了一根柱子。在这些 $(W + 1) \times (H + 1)$ 个点中，农夫约翰必须选择两个点来固定电线的两端，以便悬挂横幅。 约翰希望横幅悬挂时不受干扰，并要求在他拉紧的电线下方没有柱子。 农夫约翰需要你的帮助来计算他有多少种可能的方式来悬挂横幅。他知道这个数量很大，32 位整数可能不足以计算出答案。 考虑下面的牧场示例，其中 $W = 2$ 和 $H = 1$： \* \* \* \* \* \* 横幅的长度范围是 $2..3$。这个牧场包含 $(2+1) \times (1+1) = 6$ 个点，并且有 $\binom{6}{2} = \frac{6\times5}{2\times1} = 15$ 对不同的点对，可以在其间拉伸横幅固定电线： ```cpp (0,0)-(0,1) (0,0)-(2,1) (0,1)-(2,1) (1,1)-(2,0) (0,0)-(1,0) (0,1)-(1,0) (1,0)-(1,1) (1,1)-(2,1) (0,0)-(1,1) (0,1)-(1,1) (1,0)-(2,0) (2,0)-(2,1) (0,0)-(2,0) (0,1)-(2,0) (1,0)-(2,1) ``` 在这些点对中，只有四对的长度在 $2..3$ 的范围内： 长度 长度 (0,0)-(2,0) 2.00 (0,1)-(2,0) 2.24 (0,0)-(2,1) 2.24 (0,1)-(2,1) 2.00 在这四对中，点对 (0,0)-(2,0) 和 (0,1)-(2,1) 的连线上都有柱子，因此不合适。 所以，在 15 对点中，只有两对是合适的悬挂横幅电线的候选者。

\* 第 1 行：四个用空格分隔的整数：$W$，$H$，$L_1$ 和 $L_2$。

\* 第 1 行：一个整数，表示可能的横幅数量。

（由 ChatGPT 4o 翻译）