17386번 선분 교차 1, 17387번 선분 교차 2

https://www.acmicpc.net/problem/17386

https://www.acmicpc.net/problem/17387

선분 AB와 선분 CD가 교차하려면, 

선분 AB를 기준으로 C와의 방향과 D와의 방향이 서로 달라야 한다.

즉, CCW(A, B, C) * CCW(A, B, D)의 값이 음수여야 한다.

선분 CD의 입장에서 마찬가지이다.

CCW(C, D, A) * CCW(C, D, B)의 값이 음수여야 한다.

즉, CCW(A, B, C) * CCW(A, B, D) <= 0 && CCW(C, D, A) * CCW(C, D, B) <= 0 이면, 

교차한다고는 일단 할 수 있다.

그러나 

CCW(A, B, C) * CCW(A, B, D) == 0 && CCW(C, D, A) * CCW(C, D, B) == 0 인 경우가 있다.

아래 그림을 참고하자.

오른쪽으로 갈 수록 큰 것으로 생각하자.

두 번째 경우를 보면

점 C가 점 B보다 작아야 하며,

점 A가 D보다 작아야 한다. 

코드 27 ~ 30 번째 줄 참고.

두 문제 적용되는 정답 코드이다.

#include <bits/stdc++.h>
 
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; // 시계
}
 
bool chk(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c, pair<ll, ll> d)
{
    int abc = ccw(a, b, c);
    int abd = ccw(a, b, d);
    int cda = ccw(c, d, a);
    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);
 
        return a <= d && c <= b;
    }
 
    return abc * abd <= 0 && cda * cdb <= 0;
}
 
int main(void)
{
    pair<ll, ll> xy[4];
 
    for (int i = 0; i < 4; i++)
        scanf("%lld %lld", &xy[i].first, &xy[i].second);
    
    if (chk(xy[0], xy[1], xy[2], xy[3])) printf("1\n");
    else printf("0\n");
 
    return 0;
}