삼각형 래스터화

컴퓨터 그래픽스의 기본 연산 중 하나가 삼각형 래스터화다. 삼각형 세 꼭짓점의 픽셀 좌표가 주어지면 래스터화 알고리즘은 어떤 픽셀을 칠할지 정한다.

위 그림은 가로 10칸, 세로 12칸으로 이루어진 화면이다. 꼭짓점 좌표계는 그림처럼 픽셀의 경계선에 정수 값이 놓이고, 픽셀 중심은 반정수 좌표에 놓인다. 그림 왼쪽 위에 삼각형 세 꼭짓점의 좌표가 x 다음 y 순서로 적혀 있다. y 좌표는 아래로 갈수록 커진다. 세 꼭짓점은 그래픽스의 표준 관례대로 시계 방향으로 나열되고, 세 꼭짓점을 순환시켜 적은 입력은 같은 삼각형으로 본다.

래스터화 규칙은 하나다. 픽셀 중심이 삼각형 내부에 있거나 삼각형의 변 위에 있으면 그 픽셀을 칠하고, 아니면 칠하지 않는다. 꼭짓점 좌표가 정수이므로 픽셀 중심이 변 위에 정확히 놓이는지를 판정할 수 있고, 반드시 정확하게 판정해야 한다.

세 꼭짓점이 한 직선 위에 있으면 삼각형의 면적이 0이 되고, 세 변의 합집합은 세 꼭짓점을 모두 품는 하나의 선분이 된다. 이때는 중심이 그 선분 위에 놓인 픽셀만 칠한다.

세 꼭짓점의 좌표가 주어질 때 이 규칙으로 칠하는 픽셀의 개수를 구하라. 그림의 예에서는 픽셀 20개를 칠한다.

입력은 여러 문제로 이루어지고, 문제 하나가 한 줄을 차지한다. 각 줄은 공백으로 구분된 정수 여섯 개 $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$을 담는다. 모든 좌표는 0 이상 2000 이하다. 화면 크기는 가로 2000, 세로 2000이라고 가정한다. 문제는 최대 200개다. 여섯 개가 모두 0인 줄이 나오면 입력이 끝나고, 그 줄은 처리하지 않는다.

문제마다 칠한 픽셀의 개수를 한 줄에 출력한다.