[수학 4 단계] 백준 17387번 선분 교차 2

문제

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

 

이 문제는 3점이 일직선 일 수도 있음.

 

A와 B중 큰 것을 B, C와 D중 큰 것을 D라고 할 때

A가 D보다 작으면서 C가 B보다 작아야 함.

 

이때 pair<int,int> 를 그냥 비교가 가능한데, x,y좌표로 굳이 나눠서 비교하면

가로 일직선인 경우 세로 일직선인 경우 각각 분리해야 하므로 번거로움.

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

int CCW(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3)
{
	ll temp = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;

	temp = 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 if (temp < 0) return -1; // 시계
}

int main() {

	
	pair<int, int> A;
	pair<int, int> B;
	pair<int, int> C;
	pair<int, int> D;
	cin >> A.first >> A.second;
	cin >> B.first >> B.second;
	cin >> C.first >> C.second;
	cin >> D.first >> D.second;
	
	//ABC
	int abc = CCW(A,B,C);
	//ABD
	int abd = CCW(A,B,D);
	//CDA
	int cda = CCW(C,D,A);
	//CDB
	int cdb = CCW(C,D,B);

	if (abc * abd == 0 && cda * cdb == 0)
	{
		if (A > B)swap(A, B);
		if (C > D)swap(C, D);
		//first 비교가 아닌 것은 x가 같고 y가 달라서 일직선일 수 있으므로..
		if (A <= D && C <= B)
		{
			cout << 1 << endl;
		}
		else
		{
			cout << 0 << endl;
		}
		return 0;
	}
	

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