[C++] 백준 17387 선분2

#include <iostream>
#include <tuple>
 
std::tuple<long long, long long, long long, long long> line[2] = {};
 
bool check(std::pair<long long, long long> p1, std::pair<long long, long long> p2)
{
    if (p1.first == p2.first)
    {
        return p1.second <= p2.second;
    }
 
    return p1.first < p2.first;
}
 
int CCW(std::pair<long long, long long> p1, std::pair<long long, long long> p2, std::pair<long long, long long> p3)
{
    long long ans = (p1.first * p2.second + p2.first * p3.second + p3.first * p1.second) -
        (p2.first * p1.second + p3.first * p2.second + p1.first * p3.second);
 
    if (ans > 0)
        return 1;
 
    else if (ans < 0)
        return -1;
 
    else 
        return 0;
}
 
bool isIntersect(std::tuple<long long, long long, long long, long long> l1,
    std::tuple<long long, long long, long long, long long> l2)
{
    int std1 = CCW({std::get<0>(l1), std::get<1>(l1)}, {std::get<2>(l1), std::get<3>(l1) }, { std::get<0>(l2), std::get<1>(l2) })
        * CCW({ std::get<0>(l1), std::get<1>(l1) }, { std::get<2>(l1), std::get<3>(l1) }, { std::get<2>(l2), std::get<3>(l2) });
    int std2 = CCW({ std::get<0>(l2), std::get<1>(l2) }, { std::get<2>(l2), std::get<3>(l2) }, { std::get<0>(l1), std::get<1>(l1) })
        * CCW({ std::get<0>(l2), std::get<1>(l2) }, { std::get<2>(l2), std::get<3>(l2) }, { std::get<2>(l1), std::get<3>(l1) });
 
    if (std1 <= 0 && std2 <= 0)
    {
        if (std1 == 0 && std2 == 0) 
        { 
            if (check({ std::get<2>(l1), std::get<3>(l1) }, { std::get<0>(l1), std::get<1>(l1) }))
            {
                std::swap(std::get<0>(l1), std::get<2>(l1));
                std::swap(std::get<1>(l1), std::get<3>(l1));
            }
 
            if (check({ std::get<2>(l2), std::get<3>(l2) } ,{ std::get<0>(l2), std::get<1>(l2) }))
            {
                std::swap(std::get<0>(l2), std::get<2>(l2));
                std::swap(std::get<1>(l2), std::get<3>(l2));
            }
 
            return check({ std::get<0>(l1), std::get<1>(l1) }, { std::get<2>(l2), std::get<3>(l2) }) && 
                check({ std::get<0>(l2), std::get<1>(l2) }, { std::get<2>(l1), std::get<3>(l1) });
        }
 
        else
            return true; 
    }
 
    else 
        return false;
}
 
int main()
{
    for (int i = 0; i < 2; ++i)
    {
        std::cin >> std::get<0>(line[i]) >> std::get<1>(line[i]) >> std::get<2>(line[i]) >> std::get<3>(line[i]);
    }
 
    if (isIntersect(line[0], line[1]))
        std::cout << 1;
 
 
    else
        std::cout << 0;
 
    return 0;
}
 
 

 

이전에 풀어본 문제(선분 그룹)과 똑같습니다.

세 개의 점으로 나눠서  CCW 체크를 해보는 게 관건입니다.

두 개 다 선분 위에 있다면 선분이 평행인지, 끝점이 붙어있는지 확인합니다.

선분 두 개가 교체되는 방법은 -1 * 1(반시계, 시계) 혹은 0 * () 입니다.