boj, 백준) 17387. 선분 교차2 ( C/C++ )

1. 문제 링크

www.acmicpc.net/problem/17387

17387번: 선분 교차 2

2. 문제 개요

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다.

 

3. 문제 힌트

여러 가지 예외 케이스들을 생각해보자.

 

가장 기본적인, 두 선분이 교차하는 것에서 시작해서..

 

예제

이런 다양한 경우가 있을 수 있다. 어떻게 예외를 처리해야 할까

 

4. 문제 풀이

많은 예외처리를 다룬 선분 교차 알고리즘을 다른 블로그에서도 많이 올려놓아서 자세한 설명은 구글을 조금 찾아보면 바로 볼 수 있다!

 

우선, 가장 기본적인 교차는 외적을 통해서 할 수 있다.

(3) 번의 두 번째 예와 같이 짧은 선분을 기준으로 외적을 해보면 음수가 나와서 교차한다고 판단할 수 있지만 실제로 교차하지 않아, 큰 선분을 기준으로도 외적을 한번 더 해보아야 한다는 점,

 

한 선분에 3개의 정점이 있을 수 있기 때문에 외적의 곱이 음수뿐만 아니라 0도 포함해야 한다는 점.

 

그리고 4, 5번째 예 때문에 각 선분을 기준으로 하는 외적이 모두 0일 때를 살펴보아야 한다.

x축에 평행하게 선분이 평행하다면, 각 선분의 정점을 x축으로 정렬하여 선분의 위치를 확인해야 한다.

그 외 축이나 방향에 평행한 경우도 정점의 위치를 사용하여 4번째인지, 5번째인지 구분한다.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

struct POINT {
	long long int x, y;
};

POINT l1[2],l2[2];

int ccw(POINT a, POINT b, POINT c) {
	long long int ret = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);

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

int main()
{
	scanf("%lld %lld %lld %lld", &l1[0].x, &l1[0].y, &l1[1].x, &l1[1].y);
	scanf("%lld %lld %lld %lld", &l2[0].x, &l2[0].y, &l2[1].x, &l2[1].y);

	long long int ccw1 = ccw(l1[0], l1[1], l2[0]) * ccw(l1[0], l1[1], l2[1]);
	long long int ccw2 = ccw(l2[0], l2[1], l1[0]) * ccw(l2[0], l2[1], l1[1]);
	if (ccw1 <= 0 && ccw2 <= 0)
	{
		if (ccw1 == 0 && ccw2 == 0) {

			if (l1[0].x == l2[0].x)
			{
				if (l1[0].y > l1[1].y)
					swap(l1[0], l1[1]);

				if (l2[0].y > l2[1].y)
					swap(l2[0], l2[1]);


				if (l1[0].y <= l2[1].y && l2[0].y <= l1[1].y)
					printf("1");
				else
					printf("0");

			}
			else
			{
				if (l1[0].x > l1[1].x)
					swap(l1[0], l1[1]);

				if (l2[0].x > l2[1].x)
					swap(l2[0], l2[1]);

				if (l1[0].x <= l2[1].x && l2[0].x <= l1[1].x)
					printf("1");
				else
					printf("0");

			}
		}
		else
		{
			printf("1");
		}
	}
	else
		printf("0");


	return 0;
}

 

 

6. 결과