[BOJ/백준] 17386 - 선분 교차 1

17386번: 선분 교차 1

---

 

CCW

---

---

• 제목

선분 교차 1

---

• 조건

시간 제한 : 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	예제 출력1
1 1 5 5 1 5 5 1	1

예제 입력2	예제 출력2
1 1 5 5 6 10 10 6	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;
}