Banner

Time limit1sMemory limit128 MB

Summary

Count unordered pairs of integer grid points in a W by H post grid whose distance lies in [L1, L2] and whose connecting segment contains no other grid post.

Level: Medium7 of 10
Topics: Math, Number theory, Geometry, Brute force
Solved: No attempts yet

Problem

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 hangs between two poles on a wire whose length must lie in the range $L_1 \dots L_2$ ( $1 \le L_1 \le L_2 \le 1{,}500$ ).

The pasture measures $W \times H$ ( $1 \le W \le 1{,}000$ ; $1 \le H \le 1{,}000$ ), and Farmer John has installed a post at every point with integer coordinates. From these $(W + 1) \times (H + 1)$ points he must pick exactly two to hold the two ends of the wire.

To keep the hanging banner from being disturbed, Farmer John requires that no other post lie directly under the tight wire. In other words, no post may sit exactly on the segment joining the two chosen endpoints (the endpoints themselves do not count).

Count how many ways Farmer John can hang the banner — that is, how many unordered pairs of posts have a straight-line distance within $[L_1, L_2]$ and no other post lying on the segment between them. The answer can be large and may exceed the range of a 32-bit integer.

Worked illustration. Consider a pasture with $W = 2$ and $H = 1$ . The posts form the grid below.

* * *
* * *

Suppose the banner length must lie in $2 \dots 3$ . This pasture has $(2+1) \times (1+1) = 6$ posts and $\binom{6}{2} = 15$ candidate pairs. Only four of them have a length within $[2, 3]$ :

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

Among these four, (0,0)-(2,0) and (0,1)-(2,1) each have another post lying exactly on the segment between the endpoints, so they are unsuitable. Only the remaining two pairs are acceptable, giving the answer 2.

Input

A single line with four space-separated integers $W$ , $H$ , $L_1$ , and $L_2$ .

Output

A single integer: the number of ways the banner can be hung.

Examples5

Example 1
Input
```
2 1 2 3
```
Expected output
```
2
```
Example 2
Input
```
1 1 1 1
```
Expected output
```
4
```
Example 3
Input
```
1 1 1 2
```
Expected output
```
6
```
Example 4
Input
```
3 1 1 1
```
Expected output
```
10
```
Example 5
Input
```
10 10 5 5
```
Expected output
```
224
```