ez_code   3년 전

문제

격자점은 데카르트 좌표 시스템 상 좌표 값이 정수인 점을 말합니다. 내부 격자점은 다각형이 주어질 때 그 경계가 아닌 내부에 존재하는 격자점을 말합니다. 예를 들어, 아래 그림은 내부 격자점이 6개인 삼각형을 나타냅니다.

(그림 참조)

각 좌표 값이 100 이하 unsigned 정수인 세 쌍의 좌표 (xA, yA), (xB, yB), (xC, yC)를 입력으로 받는 프로그램을 작성합시다. 수는 한 줄에 정확히 하나의 공백으로 구분되어 있으며 xA yA xB yB xC yC 순서로 주어집니다. 좌표는 (일직선 상에 있을 수도 있는) 서로 다른 세 격자점입니다. 만약 주어진 좌표가 넓이가 0이 아닌 삼각형을 나타낼 경우, 프로그램은 화면에 삼각형의 내부 격자점의 수를 출력합니다. 그 외의 경우, 프로그램은 화면에 숫자 0을 출력합니다. (만약 세 점이 일직선 상에 있다면 내부 격자점은 존재하지 않습니다.)

입력

입력은 하나의 정수 N(0 <= N <= 255)으로 시작합니다. 이후 N개의 입력 케이스가 주어집니다. 각각의 케이스는 100을 초과하지 않는 여섯 개의 unsigned 정수입니다. 여섯 개의 정수 xA yA xB yB xC yC는 세 좌표 (xA, yA), (xB, yB), (xC, yC)에 대응됩니다.

출력

모든 입력에 대해, 한 줄에 내부 격자점의 수를 출력합니다.

댓글을 작성하려면 로그인해야 합니다.