<백준 알고리즘>CCW, 선분 교차 판별 12781번

CCW 알고리즘

counter clock wise(시계 반대 방향)

세 점이 있을 때 방향이 시계방향인지, 반시계 방향인지, 직선인지 알 수 있는 알고리즘이다.
벡터의 외적을 생각하면 쉽게 이해할 수 있다.
오른손 법칙을 이용하여 시계 반대방향엔 양의 법선이 시계 방향엔 법선이 음수로 나오고 0이 나올 경우 세 점이 직선을 이룬다는 것을 알 수 있다.

<출처>https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

int ccw(Point a, Point b, Point c) {
    long long cross = (long long)(b.x - a.x) * (c.y - a.y) - (long long)(b.y - a.y) * (c.x - a.x);
    if (cross > 0) return 1;   // 반시계 방향
    if (cross < 0) return -1;  // 시계 방향
    return 0;                  // 일직선
}

z축은 고려하지 않고 벡터 ab와 벡터 a c를 만들어 그에 대한 외적을 구한다고 생각하면 된다.

CCW를 활용한 선분 교차 판별

<출처>https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

4개의 점이 있고 그 점들로 이루어진 두개의 선분이 있을 때 점 p1,q1을 기준으로 본다면 만약 p1,q1,p2와 p1,q1,q2의 부호가 다를 경우 두 선분은 교차한다.

그러나 세 번째 case를 볼 경우 부호가 다르지만 선분이 교차하지 않는다. 이럴 경우를 대비해 p2,q2,p1과 p2,p2,q1의 부호 역시 다른지 확인 해야한다.

또한 세 점이 직선에 위치할 경우도 고려해야한다.

백준 12781번 문제

접근방법

처음엔 두 직선의 방정식이 교차하는 지점의 좌표를 구하고 이 좌표가 해당 선분의 범위에 있는지 확인하는 방식으로 구하려 하였다. 하지만 부동소수점 오차때문에 좀더 까다롭게 다뤄야 할 것 같아서 더 쉬운 방식으로 CCW알고리즘을 이용했다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>


using namespace std;

struct Point
{
	int x;
	int y;
};
 
Point point[5];

float x, y;

int ccw(Point point1,Point point2, Point point3)
{
	long long rst = (long long)(point2.x - point1.x) * (point3.y - point1.y) - (long long)(point2.y - point1.y) * (point3.x - point1.x);

	if (rst > 0)
		return 1;
	else if (rst < 0)
		return -1;
	else
		return 0;
}

bool IsInterSect()
{
	int r1 = ccw(point[1], point[2], point[3])* ccw(point[1], point[2], point[4]);
	int r2 = ccw(point[3], point[4], point[1]) * ccw(point[3], point[4], point[2]);
	
	return (r1 < 0 && r2 < 0); 
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);



	for (int i = 1; i <= 4; i++)
	{
		cin >> point[i].x >> point[i].y;
	}

	if (IsInterSect())
	{
		cout << 1;
	}
	else
	{
		cout << 0;
	}
	

	
	return 0;
}