4513 - 격자점

• Submit
• Status
• Discuss
• Summary

Description

주어진 세 꼭짓점  (x1, y1), (x2, y3), (x3, y3)을 연결하여 만들어진 도형 내부와 경계에 포함되는 정수 격자점 갯수를 구해보자.

Input

Line 1: 입력 갯수 N (0≤N≤10000)

Line 2~N+1: x1, y1, x2, y2, x3, y3

(-10000 ≤ x1, x2, x3 ≤ 10000)

(-3000 ≤ y1, y2, y3 ≤ 3000)

(x1, y1, x2, y2, x3, y3은 모두 정수)

Output

Line 1~N: 주어진 삼각형 내부의 격자점 갯수

Sample Input

4
0 0 1 0 0 1
0 0 5 0 0 5
3 0 -2 0 0 -2
0 0 -3 0 -1 1

Sample Output

3
21
10
5

Hint

* 신발끈 공식과 픽의 정리에 대해 알아보세요