[C/C++] 백준 17386, 17387번 - 선분 교차 1, 2

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<ll, ll> pll;

ll x, y;
vector<pll> v;

ll CCW(pll A, pll B, pll C)
{
	ll tmp = A.X * B.Y + B.X * C.Y + C.X * A.Y;
	tmp -= B.X * A.Y + C.X * B.Y + A.X * C.Y;

	if (tmp > 0) return 1; // 반시계
	else if (tmp == 0) return 0; // 일직선
	else if (tmp < 0) return -1; // 시계방향
}

int solve(pll A, pll B, pll C, pll D)
{
	ll ans1 = CCW(A, B, C) * CCW(A, B, D);
	ll ans2 = CCW(C, D, A) * CCW(C, D, B);

	if (ans1 == 0 && ans2 == 0) 
	{
		// pair 대소비교. 첫번째 인자가 같다면 두번째 인자 비교
		if (A > B) swap(A, B);
		if (C > D) swap(C, D);
		if (A <= D && B >= C) return 1; 
		else return 0; 
	}
	else
	{
		if (ans1 <= 0 && ans2 <= 0) return 1; 
		else return 0;
	}
	
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 4; i++)
	{
		cin >> x >> y;
		v.push_back({ x,y });
	}

	cout << solve(v[0], v[1], v[2], v[3]);
}

 

풀이 방법

 

CCW는 삼각형의 면적과 벡터 방향을 나타내는데 CCW값이 양수라면 반시계 방향, 음수라면 시계방향, 그리고 값이 0이라면 세 점이 일직선이라는 의미이다. 

 

(1) 두 선분은 일직선상에 위치하고있지만 겹치지 않을 때와 겹칠 때

CCW값은 0이며, pair 대소비교를 통해 점 B가 점 A보다 더 크게 만들어주고 점 B가 C와 D 사이에 있는지 확인한다.

 

(2) 두 선분이 교차할 때

점 A와 점 B로 만들어지는 직선을 기준으로 평면이 나눠진다고 할 때 점 C와 점 D가 다른 평면에 있다면,

CCW(A, B, C) * CCW(A, B, D) 값은 -1이 나오게 된다. 

 

(3) 두 선분이 교차하지 않을 때

 

그러나 위 처럼 점 C와 점 D가 같은 평면에 있다면 

CCW(A, B, C) * CCW(A, B, D) 값은 1이 나오게 된다.

 

그렇기 때문에 CCW(A,B,C) * CCW(A, B, D) 값과 CCW(C, D, A) * CCW(C, D, B) 값이 모두 0 이하라면
두 선분은 교차하고있다고 볼 수 있다.

 

 

 

 

www.acmicpc.net/problem/17386

17386번: 선분 교차 1

www.acmicpc.net/problem/17387

17387번: 선분 교차 2