[백준] CCW

문제

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

예제 입력 1

1 1
5 5
7 3

예제 출력 1

-1

예제 입력 2

1 1
3 3
5 5

예제 출력 2

0

예제 입력 3

1 1
7 3
5 5

예제 출력 3

1

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 기하학

시행착오

처음엔 p1과 p3를 잇는 선분의 방정식을 도출하고 p2가 그 선분을 기준으로 아래에 있는지, 위에 있는지 대입해보는 방식으로 풀었다. 그 결과 채점은 통과했지만 다른 사람의 풀이를 보니 정답과는 거리가 있었다. 아래는 내가 푼 코드이다.

#include <iostream>
#include <math.h>

using namespace std;
int main() {
	int p1x, p2x, p3x;
	int p1y, p2y, p3y;

	cin >> p1x >> p1y;
	cin >> p2x >> p2y;
	cin >> p3x >> p3y;

	if (p1x == p3x)
	{
		if (p1y > p3y)
		{
			if (p1x < p2x)
			{
				cout << -1;
			}
			else if (p1x > p2x)
			{
				cout << 1;
			}
			else
			{
				cout << 0;
			}
		}
		else
		{
			if (p1x < p2x)
			{
				cout << 1;
			}
			else if (p1x > p2x)
			{
				cout << -1;
			}
			else
			{
				cout << 0;
			}
		}
	}
	else
	{
		double a, b;
		a = (p3y - p1y) / (double)(p3x - p1x);
		b = p1y - a*p1x;
		if (p1x < p3x)
		{
			if (fabs(p2y - (a* p2x + b)) < 0.01) {
				cout << 0;
			}
			else
			{
				if (p2y < a* p2x + b)
				{
					cout << 1;
				}
				else if (p2y > a* p2x + b)
				{
					cout << -1;
				}
			}

		}
		else if (p1x > p3x)
		{
			if (fabs(p2y - (a* p2x + b)) < 0.01) {
				cout << 0;
			}
			else
			{
				if (p2y < a* p2x + b)
				{
					cout << -1;
				}
				else if (p2y > a* p2x + b)
				{
					cout << 1;
				}
				else {
					cout << 0;
				}
			}

		}
	}
	

	return 0;
}

풀이

이 문제는 벡터의 외적을 이용해 푸는 문제였다. 외적의 크기가 0보다 작으면 시계방향, 0보다 크면 반시계방향, 0이면 직선이다.

외적

외적 설명 :

https://degurii.tistory.com/47

[알고리즘] CCW로 세 점의 방향성 판별하기

두 벡터의 외적을 구하면 두 벡터에 직교하는 벡터를 얻을 수 있다.