题目背景

题目大意(by:曹彦臣)：

平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内。

题目描述

Bessie is returning from a long trip abroad, and Farmer John wants to erect a nice 'Welcome Home' banner in her pasture for her arrival. The banner will hang between two poles on a wire whose length is in the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).

The pasture's size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and Farmer John has installed a post at every point with integer

coordinates. Of these (W + 1) * (H + 1) points, Farmer John must pick just two that will hold either end of the wire from which he will hang the banner.

FJ wants no interference with his banner as it hangs and requires that no post be directly under the tight wire he stretches between the two chosen posts.

Farmer John needs your help to figure out how many possible ways he can hang the banner. He knows the number is large and that a 32-bit integer might not be sufficient to compute the answer.

Consider the example pasture below, with W = 2 and H = 1:

* * * * * * The banner size is in the range 2..3. This pasture contains (2+1) * (1+1) = 6 points and has (6 take 2) = (6*5)/(2*1) = 15 different potential pairs of points between which the banner-holding wire might stretch:

(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) 

Of these pairs, only four have a length in the range 2..3: Len Len

(0,0)-(2,0) 2.00 (0,1)-(2,0) 2.24

(0,0)-(2,1) 2.24 (0,1)-(2,1) 2.00

Of these four, the pairs (0,0)-(2,0) and (0,1)-(2,1) both have a post directly on the line between the endpoints, and thus are

unsuitable.

So, just two pairs of points out of 15 are acceptable candidates for hanging the banner wire.

输入格式

* Line 1: Four space-separated integers: W, H, L1, and L2

输出格式

* Line 1: A single integer denoting the number of possible banners

题目大意

贝西正要从一趟长途旅行中回来，Farmer John想要在她的牧场里布置一个“欢迎回家”的横幅来迎接她。这个横幅将会拴在一个范围为L1到L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500)的线的两端

牧场面积为W × H (1 <= W <= 1000;1 <= H <= 1000)，并且Farmer John在每个整数坐标的点都安装了一个杆子。在这(W + 1) * (H + 1)点中，Farmer John必须选择两个点来固定他将悬挂旗帜的线的两端。

FJ希望他的旗帜挂上去之后不会被挡住，所以在两个柱子之间的线上不能有其他柱子。

Farmer John需要你的帮助来计算出他有多少种可能的方式来悬挂横幅。他知道这个数字很大，一个32位的整数可能不足以计算出答案。

示例，W = 2, H = 1: 横幅大小在2到3的范围内。这个牧场包含(2+1)(1+1)= 6个点，并且有(6选2)=(65)/(2*1)= 15个不同的潜在点对，在这些点之间可以拉出这几条线:

(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对点中只有两对点可以作为悬挂横幅线的候选点。

2 1 2 3 

2