Triangle

http://acm.pku.edu.cn/JudgeOnline/problem?id=2954

Description

A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie completely inside of the triangle (points on the edges or vertices of the triangle do not count).

Input

The input test file will contain multiple test cases. Each input test case consists of six integers x₁, y₁, x₂, y₂, x₃, and y₃, where (x₁, y₁), (x₂, y₂), and (x₃, y₃) are the coordinates of vertices of the triangle. All triangles in the input will be non-degenerate (will have positive area), and −15000 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 15000. The end-of-file is marked by a test case with x₁ =  y₁ = x₂ = y₂ = x₃ = y₃ = 0 and should not be processed.

Output

For each input case, the program should print the number of internal lattice points on a single line.

Source

Stanford Local 2004


Solving

격자상의 세 개의 정수좌표가 주어지면 이 좌표를 꼭지점으로 하는 삼각형 내에 존재하는 정수좌표의 수를 구하여라.

모든격자를 순회하면서 격자가 삼각현 안에 있는지 밖에 있는지 검사하는 방법도 있으나 이 방법은 최대 9억개의 점을 검사해야하기 때문에 아무리 최적화를 한다고 해도 너무 오랜 시간이 걸리게 된다.

다음으로 y축을 순회하면서 y'값이 정해졌을 때 y=y'의 직선과 삼각형의 교점이 두개가 된다면 이 사이에 존재하는 x를 모두 카운트해서 구하는 방법이있다.

하지만 가장 쉬운 방법으로 픽의정리(Pick's theorem)을 이용하여 넓이를 구할 수 있다. 픽의 정리는 격자 다각형 P(모든 꼭지점의 격자점 위에 있고, 도형을 이루는 선분이 서로 교차하지 않음)의 넓이와 그 다각형 위 그리고 안에 있는 격자점의 개수 사이의 관계를 정확하게 알 수 있다. P안에 있는 격자점의 개수를 I(P), P의 경계선 위에 있는 격자점의 개수를 B(P)라 하면 P의 넓이 A(P)는 다음과 같다.

A(P) = I(P) + B(P)/2 -1

문제에선 I(P)를 구하는 것이므로 I(P) = B(P)/2 - A(P) - 1의 수식으로 구할 수 있다.

세 점의 좌표가 주어졌을 때 삼각형의 넓이는 다름과 같이 구할 수 있다.

삼각형의 넓이 A(P) = | (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3) | / 2.0

각 선분에 대해 B(P)는 기울기를 이용하여 쉽게 구할 수 있다. 두 점 p1(x1,y1), p2(x2,y2)를 잇는 선분위의 격자점의 수는 x2-x1와 y2-y1의 GCD와 같다.

#include <cstdlib> #include <cstdio> #include <cmath> #define max(a,b) (((a) > (b)) ? (a) : (b)) #define min(a,b) (((a) < (b)) ? (a) : (b)) int BP(int x1, int y1, int x2, int y2); double AP(int x1, int y1, int x2, int y2, int x3, int y3); int GCD(int a, int b) { if (b==0) return a; return GCD(b, a%b); } int main() { int x1, x2, x3; int y1, y2, y3; while (scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3)) { if (x1 == 0 && x2 == 0 && x3 == 0 && y1 == 0 && y2 == 0 && y3 == 0) break; int bp = BP(x1,y1, x2,y2) + BP(x2,y2, x3,y3) + BP(x3,y3, x1,y1) + 3; double ap = AP(x1,y1, x2,y2, x3,y3); int ip = ap - bp/2.0 + 1; //printf("%d %lf\n", bp, ap); printf("%d\n", ip); } return 0; } int BP(int x1, int y1, int x2, int y2) { int dx = abs(x2 - x1); int dy = abs(y2 - y1); int gcd = GCD(max(dx,dy), min(dx,dy)); return gcd-1; } double AP(int x1, int y1, int x2, int y2, int x3, int y3) { return abs((x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)) / 2.0; }