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

17387번: 선분 교차 2

---

CCW

---

---

• 제목

선분 교차 2

---

• 조건

시간 제한 : 0.25 초

메모리 제한 : 512 MB 

---

• 문제

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

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

---

• 입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

---

• 출력

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

---

• 제한

-1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
x1, y1, x2, y2, x3, y3, x4, y4는 정수
선분의 길이는 0보다 크다.

---

예제 입력1	예제 출력1
1 1 5 5 1 5 5 1	1

예제 입력2	예제 출력2
1 1 5 5 6 10 10 6	0

예제 입력3	예제 출력3
1 1 5 5 5 5 1 1	1

예제 입력4	예제 출력4
1 1 5 5 3 3 5 5	1

예제 입력5	예제 출력5
1 1 5 5 3 3 1 3	1

예제 입력6	예제 출력6
1 1 5 5 5 5 9 9	1

예제 입력7	예제 출력7
1 1 5 5 6 6 9 9	0

예제 입력8	예제 출력8
1 1 5 5 5 5 1 5	1

예제 입력9	예제 출력9
1 1 5 5 6 6 1 5	0

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define endl '\n'

#define pll pair<long, long>
#define pllll pair<pll, pll>
long long ccw(pll a, pll b, pll c){
	long long tmp = (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
	if(tmp > 0) return 1;
	else if(tmp < 0) return -1;
	else return 0;
}

bool isMeet(pllll a, pllll b){
	long long ccw1 = ccw(a.first, a.second, b.first) * ccw(a.first, a.second, b.second);
	long long ccw2 = ccw(b.first, b.second, a.first) * ccw(b.first, b.second, a.second);
	if(ccw1 <= 0 && ccw2 <= 0){
		if(ccw1 == 0 && ccw2 == 0){
			if(a.first > a.second) swap(a.first, a.second);
			if(b.first > b.second) swap(b.first, b.second);
			return a.first <= b.second && b.first <= a.second;
		}
		return true;
	}
	return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	long long x1, x2, y1, y2;
	pllll dot[2];
	for(int n = 0 ; n < 2 ; n++){
		cin >> x1 >> y1 >> x2 >> y2;
		dot[n] = {{x1, y1}, {x2, y2}};
	}
	cout << isMeet(dot[0], dot[1]) << endl;
    return 0;
}