도입

• 백준 2166번 문제, 11758번 문제를 풀기 위해 배운 개념을 정리한다.

개요

• CCW (Counter Clock Wise, 반시계 방향) 알고리즘은 벡터곱(외적)을 활용해 세 점의 방향을 판별하는 기하 알고리즘이다.

설명

• 경우의 수는 시계 방향, 반시계 방향, 직선으로 3가지가 있으며 외적 값이 음수면 시계, 양수면 반시계, 직선은 0일 때로 판별한다.
  
• 외적을 구하는 여러 방법이 있지만, 대수적으로는 아래 방법을 많이 사용한다.

  $\mathbf {a} = [a_1, a_2, a_3],\mathbf {b} = [b_1, b_2, b_3]$에 대하여
  ${\displaystyle \mathbf {a} \times \mathbf {b} =[a_{2}b_{3}-a_{3}b_{2},a_{3}b_{1}-a_{1}b_{3},a_{1}b_{2}-a_{2}b_{1}]}$

적용 예시

• 백준 2166번 다각형의 면적 풀이 예시

#include <iostream>
#include <utility>
#include <cmath>
#define P pair<double, double>
using namespace std;

int N;
double answer = 0;
P dot[10000];

void input()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> dot[i].first >> dot[i].second;
}

double ccw(P a, P b, P c)
{
	double outer = a.first * b.second + b.first * c.second + c.first * a.second;
	outer -= (b.first * a.second + c.first * b.second + a.first * c.second);
	return outer / 2;
}

void solve()
{
	for (int i = 1; i < N; ++i)
		answer += ccw(dot[0], dot[i - 1], dot[i]);
	cout << fixed;
	cout.precision(1);
	cout << abs(answer);
}

int main()
{
	input();
	solve();
	return 0;
}

• 백준 11758번 CCW 풀이 예시

#include <iostream>
using namespace std;

int outer;
int p1[2], p2[2], p3[2];

void input()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> p1[0] >> p1[1];
	cin >> p2[0] >> p2[1];
	cin >> p3[0] >> p3[1];
}

void ccw()
{
	outer = p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1];
	outer -= p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0];
}

void solve()
{
	ccw();

	if (outer > 0)
		cout << 1;
	else if (outer < 0)
		cout << -1;
	else
		cout << 0;
}

int main()
{
	input();
	solve();
	return 0;
}

참고

• 벡터곱 | Wikipedia
• Cross product | Wikipedia
• [기하] CCW
• [알고리즘] CCW(Counter Clock Wise)