현수막

시간 제한1초메모리 제한128 MB

요약

W 곱하기 H 격자 위의 정수 좌표 점 중에서 거리가 [L1, L2]에 들어가고 두 점을 잇는 선분 위에 다른 격자 점이 없는 순서 없는 쌍의 개수를 센다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 기하, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Bessie가 긴 해외여행을 마치고 돌아옵니다. Farmer John은 그녀를 맞이하려고 목장에 "Welcome Home" 현수막을 걸려고 합니다. 현수막은 두 기둥 사이에 걸린 철사에 매달리며, 이 철사의 길이는 $L_1 \dots L_2$ 범위 안에 있어야 합니다 ( $1 \le L_1 \le L_2 \le 1{,}500$ ).

목장의 크기는 $W \times H$ 이고 ( $1 \le W \le 1{,}000$ ; $1 \le H \le 1{,}000$ ), Farmer John은 정수 좌표를 가진 모든 지점에 기둥을 세워 두었습니다. 이 $(W + 1) \times (H + 1)$ 개의 지점 중에서 철사의 양 끝을 고정할 두 지점을 정확히 골라야 합니다.

현수막이 방해받지 않도록, Farmer John은 팽팽하게 당겨진 철사 바로 아래에 다른 기둥이 놓이지 않기를 요구합니다. 즉, 두 끝점을 잇는 선분 위(양 끝점 자체는 제외)에 다른 기둥이 정확히 놓여 있으면 안 됩니다.

현수막을 걸 수 있는 방법의 수, 곧 두 기둥 사이의 직선 거리가 $[L_1, L_2]$ 안에 있으면서 그 선분 위에 다른 기둥이 없는, 순서를 구분하지 않는 기둥 쌍의 개수를 세십시오. 답은 매우 클 수 있으며 32비트 정수의 범위를 넘을 수 있습니다.

예시 설명. $W = 2$ , $H = 1$ 인 목장을 생각해 봅시다. 기둥들은 아래와 같은 격자를 이룹니다.

* * *
* * *

현수막 길이가 $2 \dots 3$ 범위여야 한다고 합시다. 이 목장에는 $(2+1) \times (1+1) = 6$ 개의 기둥이 있고, 가능한 쌍은 $\binom{6}{2} = 15$ 개입니다. 이 중에서 길이가 $[2, 3]$ 안에 드는 것은 네 개뿐입니다.

쌍	길이
(0,0)-(2,0)	2.00
(0,0)-(2,1)	2.24
(0,1)-(2,0)	2.24
(0,1)-(2,1)	2.00

이 네 개 중에서 (0,0)-(2,0)과 (0,1)-(2,1)은 두 끝점을 잇는 선분 위에 다른 기둥이 정확히 놓이므로 사용할 수 없습니다. 남은 두 쌍만이 조건을 만족하므로 답은 2입니다.

입력

한 줄에 네 정수 $W$ , $H$ , $L_1$ , $L_2$ 가 공백으로 구분되어 주어집니다.

출력

현수막을 걸 수 있는 방법의 수를 나타내는 정수 하나를 출력합니다.

예제5

예제 1
입력
```
2 1 2 3
```
예상 출력
```
2
```
예제 2
입력
```
1 1 1 1
```
예상 출력
```
4
```
예제 3
입력
```
1 1 1 2
```
예상 출력
```
6
```
예제 4
입력
```
3 1 1 1
```
예상 출력
```
10
```
예제 5
입력
```
10 10 5 5
```
예상 출력
```
224
```