CCW / Counter Clockwise
CCW란?
평면 위에 놓여진 세 점의 방향관계를 구할 수 있는 알고리즘
벡터의 외적
외적의 결과로 외적에 쓰인 두 벡터와 동시에 수직인 벡터를 구할 수 있다. 이 수직벡터의 방향으로 세 점의 방향을 판단 할 것이다. +) 외적은 교환법칙 성립 X (크기는 같음) +) 단위벡터 : 길이가 1인 벡터
방향은 오른손 법칙을 따른다.
좀 더 부가적인 설명을 해보자면, 두 벡터의 결과를 행렬식으로 나타내어보자.
여기서 S의 부호에 따라서 세가지로 나눈다.
•
s > 0 : 반시계방향
•
s = 0 : 일직선
•
s < 0 : 시계방향
구조체 구현
struct pos {
int x,y;
};
C++
복사
간단하게 x,y좌표로 나타내었다. 매번 pair만 썼는데 구조체 깔끔하고 좋은 듯.
핵심 코드
long long tmep = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
C++
복사
행렬식을 그대로 이용하여 코드를 짰다. 깔끔하다.
내 코드
long long temp = a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
C++
복사
나는 저 방법을 알기전에 신발끈 공식을 이용하여 코드를 짰다. 다만 코드가 길어지니 나도 다음부터는 위 코드를 이용할 생각이다.
전체코드
#include <iostream>using namespace std;
struct pos {
int x,y;
};
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
pos a,b,c;
cin>>a.x>>a.y;
cin>>b.x>>b.y;
cin>>c.x>>c.y;
long long temp = a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
if (temp < 0)
cout<<"-1";
else if (temp > 0)
cout<<"1";
else
cout<<"0";
return 0;
}
C++
복사
