백준 17386 - 선분 교차 1 (C++)

 

위 그림과 같이 두개의 선분이 주어졌을 때, 왼쪽처럼 두 선분이 만나고 있다면 1을 출력하고

오른쪽처럼 만나지 않는다면 0을 출력하면 되는 문제이다.

 

 

 

문제 풀이

---

 

이 문제는 CCW알고리즘을 활용하면 간단하게 풀 수 있는 문제이다.

CCW알고리즘을 모른다면, CCW알고리즘을 먼저 알아보고 오자.

알고리즘 - CCW (세 점의 방향 판별하기) (tistory.com) 해당 링크는 필자가 작성한 CCW알고리즘 설명이다.

 

 

먼저, 처음에 주어지는 4점의 위치관계를 그림으로 보자.

 

 

입력 받은 순서에 따라 4점을 A,B,C,D 라고 했을 때, 두 선분이 만난다면 위와 같은 위치관계를 가지게 될 것이다.

(물론, 수직이 아니라 다른 형태로 만날 수도 있지만 크게 봤을 때 위치관계가 위와 유사할 것이다.)

 

이 때, 두 선분이 어떤 모양으로 만나든 반드시 성립해야 하는 조건이 2가지가 있다.

 

1. 점C와 점 D는 선분 AB를 기준으로 서로 반대쪽에 위치해야 한다.

위의 그림처럼, 점 CD가 모두 AB를 기준으로 왼쪽에 위치하거나 오른쪽에 위치한다면 두 선분은 만난다고 할 수 없을 것이다.

(정확하게는 왼쪽 오른쪽이라기보다는, 직선 AB에 의해 분할되는 두 영역이 있다면, C와 D는 서로 같은 영역에 위치해서는 안된다.)

 

즉, ABC 세점의 위치관계가 반시계 방향이라면, ABD는 시계방향이어야 하고, 반대로 ABC가 시계방향이라면 ABD는 반시계 방향이어야 한다.

해당 그림처럼, ABC와 ABD는 서로 반대 방향으로 위치해야 한다.

CCW를 이용하여, ABC와 ABD의 위치관계를 판별한 뒤 서로 다르다면 두 선분이 만난다고 할 수 있을 것 같다.

 

하지만, 1가지 예외가 있다.

 

이런 경우를 보자.

분명, ABC과 ABD는 서로 반대의 위치관계를 가지고 있지만 두 선분은 만나지 않는다.

그렇기 때문에, 고려해야 하는 것이 한가지 더 생긴다.

 

 

이렇게, CDB와 CDA의 위치관계로 함께 고려하는 것이다.

4점의 위치관계를 모두 고려하게 되면 아래와 같은 명제를 세울 수 있다.

 

(CBD와 CBA의 위치관계가 서로 반대이다) && (ABC와 ABD의 위치관계가 서로 반대이다)

== 두 선분이 만난다.

 

 

풀이 코드

---

 

struct Point
{
	long long X = 0;
	long long Y = 0;
};

struct Line
{
	Point Start;
	Point End;
};

 

먼저, 점의 위치 X,Y를 담을 Point 구조체를 선언하였고, 선분의 시작과 끝이 되는 두 점을 담을 Line구조체를 선언하였다.

 

Line Line_1;
Line Line_2;

std::cin >> Line_1.Start.X >> Line_1.Start.Y;
std::cin >> Line_1.End.X >> Line_1.End .Y;

std::cin >> Line_2.Start.X >> Line_2.Start.Y;
std::cin >> Line_2.End.X >> Line_2.End.Y;

 

이후, 입력값을 저장해주자.

 

다음은, CCW알고리즘을 이용하여 시계방향인지 반시계방향인지 판별하는 함수를 만들어보자.

bool isClockWise(Point _First, Point _Second, Point _Third)
{
	Point Vector_1 = { _Second.X - _First.X, _Second.Y - _First.Y };
	Point Vector_2 = { _Third.X - _Second.X, _Third.Y - _Second.Y };

	long long CrossZ = { Vector_1.X * Vector_2.Y - Vector_1.Y * Vector_2.X };

	return CrossZ < 0;
}

 

정말 간단하다.

먼저 세 점을 입력받는다.

 

세 점을 외적하여 나온 벡터의 Z값이 양수인지 음수인지만 검사하면 되기 때문에 Z값에 대해서만 외적을 진행하고,

그 값이 양수인지 음수인지에 따라 bool값을 반환하였다.

 

해당 함수는 시계방향인가? 라는 이름으로 만들었기 때문에 Z값이 음수라면 true를 반환하도록 하였다.

 

그 다음은 위에서 그림으로 보았던 4가지의 위치관계를 구해서 확인해보면 된다.

bool isClockWise_1 = isClockWise(Line_1.Start, Line_1.End, Line_2.Start);
bool isClockWise_2 = isClockWise(Line_1.Start, Line_1.End, Line_2.End);

if (isClockWise_1 == isClockWise_2)
{
    std::cout << 0;
    return 0;
}

bool isClockWise_3 = isClockWise(Line_2.Start, Line_2.End, Line_1.Start);
bool isClockWise_4 = isClockWise(Line_2.Start, Line_2.End, Line_1.End);

if (isClockWise_3 == isClockWise_4)
{
    std::cout << 0;
    return 0;
}

std::cout << 1;

return 0;

 

먼저, 한 선분의 Start, End를 기준으로 다른 선분의 두 점에 대해 위치관계가 반대인가를 검사하였다.

두 위치관계가 만약 동일하다면, 다른 검사를 할 필요도 없이 두 선분은 만나지 않기 때문에 0을 출력하고 함수를 종료해주었다.

 

여기서 함수가 끝나지 않았다면, 다른 선분을 기준으로 다시 위치관계를 검사해준다.

여기서도 마찬가지로 위치관계가 동일하게 나왔다면 0을 출력하고 함수를 종료해주었다.

 

만약, 여기서 함수가 종료되지 않았다면 1을 출력해주면 된다.

 

외적을 활용하여 간단하게 풀 수 있는 문제였다.

 

본인은 이 문제에서 정말 여러 번 틀렸는데, 이유는 아주 단순한 이유였다.

struct Point
{
	long long X = 0;
	long long Y = 0;
};

이렇게, 위치를 저장하는 값은 long long 이어야 한다....

본인은 int로 했다가 계속 틀려서 머리가 터질 뻔 했다.

 

다들 본인처럼 실수하지 말고 문제를 풀 땐 자료형의 범위 주어진 입력값의 범위를 잘 비교해보자.