Project Euler #102 (Triangle containment)

문제는 https://projecteuler.net/problem=102, 그리고 언어는 C를 사용하였다.

문제를 해결하기 위해 가장 필요한 함수는 특정한 점(x0, y0)이 삼각형 ABC안에 있나 없나 확인하는 부분이다.

방향벡터의 외적으로도 풀 수 있다(http://blog.naver.com/kimrip/40159510013)

여기서는 이해하기 쉬운 방법을 소개한다.

삼각형을 살피기 전에 중학교때 배운 "부등식의 영역"을 복습해보자. http://mathbang.net/466

---

우선 두 점 (x1, y1), (x2, y2)를 지나는 직선의 방정식을 구해보자.

결과를 알더라도 한번 유도해보는 차원에서 살펴보자.

두 점을 지나는 직선을 

라고 둘 때, a를 기울기, b를 절편이라고 한다.

즉 x = 0 일때의 y의 값이 b가 된다. 이 부분이 이번 문제에서 중요하게 사용될 것이다.

그러면

, 

이렇게 두 개의 방정식이 만들어 지고, 이를 풀면

, 

으로 구해진다.

자, 그러면 이제 점 (x3, y3)가 에 대해 위에 존재하는지, 아래에 존재하는지 결과를 리턴하는 함수를 구상해보자.

위의 링크에서 보듯이

처럼 빨간색으로 색칠된 부분에 있을 때 로 된다.

다시말해, 일 때, 그 점은 직선보다 y축으로 위쪽에 있다.

반대로 이면 그 점은 직선보다 y축으로 아래쪽에 위치한다.

이 공식들을 정리하면

y축으로 위쪽에 위치: 

y축으로 아래쪽에 위치: 

이다. 이 부분을 C함수로 구현하면 아래와 같다.

bool isUpper(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1)*(y3 - y1) > (y2 - y1)*(x3 - x1);
}

bool isLower(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1)*(y3 - y1) < (y2 - y1)*(x3 - x1);
}

---

이제는 원점이 삼각형 안에 들어가는가 여부를 결정하는 방법에 대해 생각해보자.

바로 아래의 방법을 보기 보다는 여러 삼각형들을 그려도 보며 먼저 생각해보시길 바란다.

내가 떠올린 방법은 "삼각형을 2등분 하는 것"이다.

우선 x축의 순으로 세 점 A, B, C를 정렬한다.

그리고 아래의 두 가지 삼각형으로 분류한다. (그림은 https://www.math10.com/en/geometry/geogebra/geogebra.html으로 그렸다)

 

두 삼각형의 차이는 점 B가 AC직선 위에 위치하느냐, 아래에 위치하느냐이다.

그러면 x축으로 x < xb인 공간과, xb <= x인 공간으로 나뉘어진다.

 

그럼 나누어진 두 삼각형 중에서 원점을 가질 가능성이 있는 부분은 B의 x좌표값에 따라 달라진다.

즉, bx <= 0이면 나누어진 부분 중 오른쪽에서 삼각형을 이루는 두 직선 사이에 (0, 0)이 존재하는지 살펴보면 되고,

반대의 경우, bx > 0이면 나누어진 부분 중 왼쪽의 삼각형을 이루는 두 직선 사이에서 (0, 0)이 존재하는지 보면 된다.

이 성질을 이용하여 코딩으로 구현하면 된다.

다만, 나는 코딩할 때 직선 AB, AC, BC에 대한 (0, 0)의 위치를 나타내는 bool 변수 u1, u2, u3, l1, l2, l3를 만들어

u1이면 AB직선 보다 y축으로 위에, l1이면 AB직선보다 아래에 있음을 알리는 flag를 미리 만들고 작업했다.

코드를 잠깐 살펴보면

bool includeOrigin(int ax, int ay, int bx, int by, int cx, int cy) {
	bool u1 = isUpper(ax, ay, bx, by, 0, 0),
		 u2 = isUpper(ax, ay, cx, cy, 0, 0),
		 u3 = isUpper(bx, by, cx, cy, 0, 0),
		 l1 = isLower(ax, ay, bx, by, 0, 0),
		 l2 = isLower(ax, ay, cx, cy, 0, 0),
		 l3 = isLower(bx, by, cx, cy, 0, 0);

	if(isLine(ax, ay, bx, by, cx, cy))
		return false;

	if ((u1 && u2 && u3) || (l1 && l2 && l3))
		return false;
	
	
	if (isUpper(ax, ay, cx, cy, bx, by)) {
		if (bx <= 0) {
			if (l3 && u2) return true;
		}
		else {
			if (l1 && u2) return true;
		}
	}
	if (isLower(ax, ay, cx, cy, bx, by)) {
		if (bx <= 0) {
			if (l2 && u3) return true;
		}
		else {
			if (u1 && l2) return true;
		}
	}

	return false;
}

여기서 isLine은 혹시나 A, B, C가 한 직선위에 있는지를 알리는 함수이며, 이 경우 false값을 리턴한다.

그리고 (0, 0)에 대해 u1, u2, u3, l1, l2, l3를 구한 결과

(u1 && u2 && u3) || (l1 && l2 && l3), 즉 모든 직선보다 위에 또는 아래에 존재하면 삼각형 안에 존재하지 않는다.

그 이후 만약 점 B가 직선 AC위에 존재할 경우

만약 bx <= 0 일 때, (오른쪽 삼각형을 볼 차례) 직선 BC보다 (0, 0)이 아래에 있고, AC보다 (0, 0)이 위에 있으면

(0, 0)은 삼각형 안에 존재한다는 것을 가지고 첫번째 true값을 리턴하는 것을 볼 수 있다.

아래에는 전체 코드이다.

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <windows.h>

bool isLine(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1)*(y3 - y1) == (y2 - y1)*(x3 - x1);
}

bool isUpper(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1)*(y3 - y1) > (y2 - y1)*(x3 - x1);
}

bool isLower(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1)*(y3 - y1) < (y2 - y1)*(x3 - x1);
}

bool includeOrigin(int ax, int ay, int bx, int by, int cx, int cy) {
	bool u1 = isUpper(ax, ay, bx, by, 0, 0),
		 u2 = isUpper(ax, ay, cx, cy, 0, 0),
		 u3 = isUpper(bx, by, cx, cy, 0, 0),
		 l1 = isLower(ax, ay, bx, by, 0, 0),
		 l2 = isLower(ax, ay, cx, cy, 0, 0),
		 l3 = isLower(bx, by, cx, cy, 0, 0);

	if(isLine(ax, ay, bx, by, cx, cy))
		return false;

	if ((u1 && u2 && u3) || (l1 && l2 && l3))
		return false;
	
	
	if (isUpper(ax, ay, cx, cy, bx, by)) {
		if (bx <= 0) {
			if (l3 && u2) return true;
		}
		else {
			if (l1 && u2) return true;
		}
	}
	if (isLower(ax, ay, cx, cy, bx, by)) {
		if (bx <= 0) {
			if (l2 && u3) return true;
		}
		else {
			if (u1 && l2) return true;
		}
	}

	return false;
}

void swap(int &x1, int &y1, int &x2, int &y2) {
	int xt, yt;
	xt = x1; yt = y1;
	x1 = x2; y1 = y2;
	x2 = xt; y2 = yt;
}

void main() {
	printf("%s\n",(includeOrigin(-340,495,-153,-910,835,-947)?"TRUE":"FALSE"));// TRUE
	printf("%s\n",(includeOrigin(-175,41,-421,-714,574,-645)?"TRUE":"FALSE"));// FALSE

	FILE *input;
	int ax, ay, bx, by, cx, cy, tx, ty, count = 0;
	input = fopen("p102_triangles.txt", "rt");
	//printf("input = %s\n", (input == NULL ? "NULL" : "OPENED"));
	
	while (fscanf(input, "%d,%d,%d,%d,%d,%d\n",&ax,&ay,&bx,&by,&cx,&cy) != EOF) {
		if (bx <= ax && bx <= cx) {
			swap(ax, ay, bx, by);
		}
		else if(cx <= ax && cx <= bx) {
			swap(ax, ay, cx, cy);
		}

		if (cx <= bx) {
			swap(bx, by, cx, cy);
		}

		if (includeOrigin(ax, ay, bx, by, cx, cy))
			count++;
	}

	printf("count = %d\n", count);
	system("pause");
}

(#ifdef _MSC_VER

#define _CRT_SECURE_NO_WARNINGS

#endif는 Visual Studio에서 파일 포인터 fopen등의 함수를 사용하기 위해 삽입한 부분이다.)