17387 선분 교차 2(기하학) [Gold II]

17387번: 선분 교차 2 (acmicpc.net)

 

11758 CCW (기하학) [Gold V]

 

두개의 점(x,y)으로 만들어진 선을 두개 입력 받아서

두 선이 교차 하는지 아닌지 체크하는 문제입니다.

CCW를 이용하면 쉽게 풀 수 있습니다.

 

풀이법

두 개의 선이 만약 교차 할 때의 경우를 생각해보겠습니다.

선 ㄱ과 ㄴ이 있다고 가정하고 ㄱ은 두개의 벡터 A, B ㄴ은 C, D로 이루어져 있다고 가정하겠습니다.

 

ㄱ과 ㄴ이 교차하는 상황에서 A,B, C와 A,B, D의 방향은 한쪽은 시계 방향, 한쪽은 반시계 방향으로 반대일 것입니다.

즉 CCW 공식으로 계산 후 두 값을 곱하면 무조건 음수가 나오는데 이것을 이용하면 쉽게 풀 수 있을 것 같습니다.

 

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm> 

using namespace std;

long v[4][2];

int CCW(long v1[2], long v2[2], long v3[2]);
bool isCross();
bool isOverlab();

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

        for (int i = 0; i < 4; i++)
        { 
                int a, b;
                cin >> a >> b;
                v[i][0] = a;
                v[i][1] = b;
        }

        int result = isCross() ? 1 : 0;
        cout << result << "\n"; 
} 

int CCW(long v1[2], long v2[2], long v3[2])
{ 
        long result = (v1[0] * v2[1] + v2[0] * v3[1] + v3[0] * v1[1]) - (v1[0] * v3[1] + v2[0] * v1[1] + v3[0] * v2[1]);
        return result > 0 ? 1 : result < 0 ? -1 : 0;
}
 
bool isOverlab()
{
        if (min(v[0][0], v[1][0]) <= max(v[2][0], v[3][0]) && min(v[2][0], v[3][0]) <= max(v[0][0], v[1][0]))
        {
                if (min(v[0][1], v[1][1]) <= max(v[2][1], v[3][1]) && min(v[2][1], v[3][1]) <= max(v[0][1], v[1][1]))
                        return true; 
        }
        return false;
} 
 
bool isCross()
{ 
        int abc = CCW(v[0], v[1], v[2]); 
        int abd = CCW(v[0], v[1], v[3]);
        int cda = CCW(v[2], v[3], v[0]);
        int cdb = CCW(v[2], v[3], v[1]); 

        if (abc * abd == 0 && cda * cdb == 0) { 
                return isOverlab();
        }
        else if (abc * abd <= 0 && cda * cdb <= 0)
                return true;
        else
                return false;
}