백준 17387 - 선분 교차 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

CCW를 이용한 선분 교차 판정 문제입니다.

선분이 나타날 수 있는 2경우입니다.(두 선분이 겹치는 경우는 제외했습니다,)

선분이 교차되는 경우와 아닌 경우가 있습니다.
여기서 확인할 수 있는 것은 한 점에서 다른 선분을 향할 때의 방향이 다르면 선분이 교차하지 않는다는 것입니다.
어느 점에서의 방향을 구하는 방법은 CCW입니다.

따라서 A,B,C / A,B,D의 CCW를 구한 뒤, 곱한 것과 C,D,A / C,D,B를 구한뒤 곱한 것이 0또는 음수가 나온다면?
-> 두 선분이 교차함을 알 수 있습니다.

이번에는 겹치는 경우입니다.

두 선분이 겹치는 경우는, 한 좌표가 다른 선분의 속에 있을 경우입니다.
이때는 두 선분의 CCW값이 모두 0이여야 합니다


자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<LL, LL>
#define F first
#define S second

using namespace std;

pp X1, X2, Y1, Y2;

int get_ccw(pp x, pp y, pp z){
    LL ans = 0;
    ans += (x.F*y.S + y.F*z.S + z.F*x.S);
    ans -= (y.F*x.S + z.F*y.S + x.F*z.S);
    if(ans > 0) return 1;
    else if(ans == 0) return 0;
    else return -1;
}

void solve(){
    int ab_cd = get_ccw(X1, X2, Y1) * get_ccw(X1, X2, Y2);
    int cd_ab = get_ccw(Y1, Y2, X1) * get_ccw(Y1, Y2, X2);
    if(ab_cd == 0 && cd_ab == 0){
        if(X1 > X2) swap(X1, X2);
        if(Y1 > Y2) swap(Y1, Y2);
        if(X2 >= Y1 && X1 <= Y2) cout << "1";
        else cout << "0";
    }
    else if(ab_cd <= 0 && cd_ab <= 0) cout << "1";
    else cout << "0";
}

int main() {
    cin.tie(0);
	cout.tie(0);
	cin >> X1.F >> X1.S;
	cin >> X2.F >> X2.S;
	cin >> Y1.F >> Y1.S;
	cin >> Y2.F >> Y2.S;
    solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요