[수학 4 단계] 백준 17386번 선분 교차 1

문제

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

 

이 상황이 되려면 CDA의 방향과 CDB의 방향이 반대가 되어야 함.

이는 위에서도 성립하므로 ABC와 ABD도 반대면 교차

하지만 이것은 어떤 3점도 일직선이지 않은 상태일 때 ABC*ABD < 0 이고 CDA*CDB < 0 인 것을 말함.

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


long long CCW(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3)
{
	long long a = x1 * y2 + x2 * y3 + x3 * y1;
	long long b = y1 * x2 + y2 * x3 + y3 * x1;
	if (a - b < 0)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

int main() {

	int x1, x2, x3, x4 , y1, y2, y3, y4;
	cin >> x1 >> y1 >> x2 >> y2;
	cin >> x3 >> y3 >> x4 >> y4;
	
	//ABC
	long long abc = CCW(x1, y1, x2, y2, x3, y3);
	//ABD
	long long abd = CCW(x1, y1, x2, y2, x4, y4);
	//CDA
	long long cda = CCW(x3, y3, x4, y4, x1, y1);
	//CDB
	long long cdb = CCW(x3, y3, x4, y4, x2, y2);

	if (abc * abd <= 0 && cda * cdb <= 0)
	{
		cout << 1 << endl;
	}
	else
		cout << 0 << endl;
}