[백준 C++] 17387번: 선분 교차 2

1. 문제

https://www.acmicpc.net/problem/17387

 

2. 알고리즘 분류

• 기하학
• 많은 조건 분기
• 선분 교차 판정

 

3. 소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

pair<long long, long long> A;
pair<long long, long long> B;
pair<long long, long long> C;
pair<long long, long long> D;

// CCW(Counter ClockWise) 알고리즘
int ccw(pair<long long, long long> p1, pair<long long, long long> p2, pair<long long, long long> p3)
{
	// 외적 계산
	long long temp = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
	temp -= p1.second * p2.first + p2.second * p3.first + p3.second * p1.first;

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

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

	int ret = 0;

	cin >> A.first >> A.second;
	cin >> B.first >> B.second;
	cin >> C.first >> C.second;
	cin >> D.first >> D.second;

	if (A > B) swap(A, B);
	if (C > D) swap(C, D);

	int ans1 = ccw(A, B, C) * ccw(A, B, D);
	int ans2 = ccw(C, D, A) * ccw(C, D, B);

	if (ans1 == 0 && ans2 == 0) {

		// 두 직선이 겹칠 때,
		if (A <= D && B >= C)
			ret = 1;
	}
	else {
		// 두 직선이 교차할 때,
		if (ans1 <= 0 && ans2 <= 0)
			ret = 1;
	}

	cout << ret;

	return 0;
}

 

4. 유용한 알고리즘

 1) CCW (Counter ClockWise) 알고리즘

1. 세 점의 방향관계를 알 수 있는 알고리즘

•  https://uigwonblog.tistory.com/88

[알고리즘] CCW(Counter ClockWise) 기하 알고리즘

• 자세한 해설
• https://howudong.tistory.com/317

[C++] 백준/BOJ - 17387 : 선분 교차 2