Crazy Dreamoon

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

요약

2000x2000 격자에 최대 2000개의 선분이 주어질 때, 적어도 하나의 선분이 내부를 지나는 격자 칸의 수를 센다.

난이도: 어려움10점 중 8점
유형: 기하, 수학, 구현, 정렬
정답자: 아직 제출이 없습니다

문제

Dreamoon은 알고리즘 대회를 아주 좋아한다. 그런데 대회에서 어떤 문제도 해결 방법을 떠올리지 못해 미칠 것 같을 때, 그는 계산지 위에 의미 없는 선분을 잔뜩 긋곤 한다.

Dreamoon의 계산지는 특별하다. 좌표가 $[0, 2000] \times [0, 2000]$ 범위인 직교좌표계 평면이라고 생각하면 된다. 격자선은 0 이상 2000 이하의 모든 정수 $c$ 에 대해 $x = c$ 또는 $y = c$ 꼴인 직선이다. 따라서 격자에는 $2000 \times 2000$ 개의 정사각형이 있다.

이제 Dreamoon은 그가 그은 선분 중 적어도 하나가 지나는 격자 정사각형이 몇 개인지 궁금해졌다. Dreamoon을 도와 답을 구하자. 격자 정사각형의 변에 닿기만 하는 것은 그 정사각형을 지나는 것으로 치지 않는다.

입력

첫째 줄에는 Dreamoon이 그은 선분의 개수 $N$ 이 주어진다. 이어지는 $N$ 개 줄 중 $i$ 번째 줄에는 네 정수 $x_{i1}, y_{i1}, x_{i2}, y_{i2}$ 가 주어지며, 이는 Dreamoon이 그은 $i$ 번째 선분이 점 $(x_{i1}, y_{i1})$ 과 점 $(x_{i2}, y_{i2})$ 를 잇는 선분임을 뜻한다.

출력

Dreamoon이 그은 선분 중 적어도 하나가 지나는 격자 정사각형의 개수를 한 줄에 출력한다.

제한

$1 \le N \le 2 \times 10^3$
$0 \le x_{i1}, y_{i1}, x_{i2}, y_{i2} \le 2 \times 10^3$
입력으로 주어지는 모든 선분의 길이는 0이 아니다

예제3

예제 1
입력
```
3
0 0 5 5
0 5 5 0
0 5 5 0
```
예상 출력
```
9
```
예제 2
입력
```
1
0 0 4 3
```
예상 출력
```
6
```
예제 3
입력
```
2
0 0 4 3
1 0 3 3
```
예상 출력
```
6
```