[알고리즘] CCW (기하, boj-11758)

문제

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을 출력한다.

 

#include <iostream>

struct	Point
{
	int	x;
	int	y;
};

double	get_dir(Point p1, Point p2, Point p3)
{
	double	direction = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
	return (direction);
}

int	main(void)
{

	Point	p1;
	Point	p2;
	Point	p3;

	//입력 받기
	std::cin >> p1.x >> p1.y;
	std::cin.ignore();
	std::cin >> p2.x >> p2.y;
	std::cin.ignore();
	std::cin >> p3.x >> p3.y;

	//선분과 점의 방향 계산
	double direction = get_dir(p1, p2, p3);

	//일직선
	if (direction == 0)
		std::cout << "0" << std::endl;
	//시계
	else if (direction < 0)
		std::cout << "-1" << std::endl;
	//반시계
	else if (direction > 0)
		std::cout << "1" << std::endl;
		
}

 

벡터에 대한 기본적인 개념이 필요했다..

(점 p1과 p2 사이의 벡터) 와 (점 p1과 p3 사이의 벡터)를 크로스 프로덕트 한 결과값을 통해 두 벡터가 시계 방향인지 반시계 방향인지, 평행한지 판정할수 있다.