BOJ 17387, 17386번 선분 교차

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

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

 

삼각형의 면적 + 벡터의 식을 나타내는 CCW 를 이용하여 문제를 해결하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<long long, long long> xy;
 
long long ccw(xy a, xy b, xy c) {
    long long ans = (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
    if (ans < 0) return -1;
    else if (ans > 0) return 1;
    return 0;
}
 
long long check(xy a, xy b, xy c, xy d) {
    long long ans1 = ccw(a, b, c) * ccw(a, b, d);
    long long ans2 = ccw(c, d, a) * ccw(c, d, b);
    if (ans1 == 0 && ans2 == 0) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        if (a <= d && b >= c) return 1;
        else return 0;
    }
    if (ans1 <= 0 && ans2 <= 0) return 1;
    else return 0;
}
 
int main() {
    xy a, b, c, d;
    cin >> a.first >> a.second >> b.first >> b.second;
    cin >> c.first >> c.second >> d.first >> d.second;
 
    printf("%lld", check(a, b, c, d));
    return 0;
}