[BOJ 7694 // C++] Triangle

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7694번 문제인 Triangle이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/7694 

7694번: Triangle

 

주어진 좌표의 범위가 작다는 점을 이용해 범위 내의 각 정수 $x$에 대하여 $(x,y)$가 삼각형 내부에 있는 격자점이 되는 범위 내의 정수 $y$의 개수를 계산해 합하는, $x$좌표의 범위에 비례한 선형 풀이로도 문제를 해결할 수 있을 것으로 예상되지만, 이 글에서는 다른 풀이인 픽의 정리(Pick's Theorem)을 이용한 풀이를 알아보자.

 

픽의 정리는 격자점만을 꼭짓점으로 갖는 단순다각형(simple polygon)의 넓이 $A$와 다각형의 경계에 있는 격자점의 개수 $b$, 그리고 내부에 있는 격자점의 개수 $i$에 대하여 $A=i+\frac{b}{2}-1$과 같은 관계식이 성립한다는 내용을 담고 있다. 삼각형의 넓이는 사선공식(shoelace formula)을 이용해 어렵지 않게 구할 수 있고 다각형의 경계에 있는 격자점의 개수는 각 변(선분) 위의 격자점의 개수를 구하는 것으로 간단히 구할 수 있다는 점을 관찰하면, 다각형 내부의 격자점의 개수는 픽의 정리를 통해 어렵지 않게 구할 수 있음을 관찰할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int X1, Y1, X2, Y2, X3, Y3;
int A;

void solve() {
	A = abs(X1 * Y2 + X2 * Y3 + X3 * Y1 - X1 * Y3 - X2 * Y1 - X3 * Y2);
	int b = 0;
	{
		int dx = abs(X2 - X1), dy = abs(Y2 - Y1);
		b += gcd(dx, dy);
	}
	{
		int dx = abs(X3 - X2), dy = abs(Y3 - Y2);
		b += gcd(dx, dy);
	}
	{
		int dx = abs(X1 - X3), dy = abs(Y1 - Y3);
		b += gcd(dx, dy);
	}

	cout << (A - b + 2) / 2 << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
	while (X1 || Y1 || X2 || Y2 || X3 || Y3) {
		solve();
		cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
	}
}