[C++] 20149번 선분 교차 3 - 기하학, 많은 조건 분기, 선분 교차 판정

1. 문제

• 2차원 좌표 평면 위 두 선분 \(L_{1}, L_{2}\)가 주어졌을 때 두 선분의 교차 여부를 판단하자. 한 선분의 각 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

<입력>

• - 1 -   \(x_{1}, y_{1}, x_{2}, y_{2}\)
• - 2 -   \(x_{3}, y_{3}, x_{4}, y_{4}\)
  • \((-1,000,000 \leq x_{i}, y_{i} \leq 1,000,000), (x_{i}, y_{i} \in \mathbb{Z}), (0 < l_{1}, l_{2})\)

<출력>

• - 1 -   교차하면 1, 아니면 0을 출력
• - 2 -   교차하는 점의 x좌표와 y좌표 출력

2. 재정의

• 교차점 구하기

3. 해결 방법

• CCW로 적절히 하면 되는데 너무 조건 분기가 많아서 생략하고 아래 링크해둔 사이트를 보고 생각하시면 되겠습니다.

4. 실수한 점, 개선할 점

• 고칠 건 많습니다. 주석도 안달았는데 코드 겁나 긴거 보소 ㄷㄷ;;

 

<코드>

#include <iostream>

#define ll long long
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define fi first
#define se second

using namespace std;

const int INF = 1187654321;

// <문제>
// 좌표
pll p1, p2, p3, p4;

// CCW
int CCWres[4];

int res;
pdd resp;

int CCW(pll p1, pll p2, pll p3) {
    ll crossProduct = p1.fi*p2.se + p2.fi*p3.se + p3.fi*p1.se;
    crossProduct -= p1.fi*p3.se + p2.fi*p1.se + p3.fi*p2.se;
    
    if(crossProduct > 0)
        return 1;
    else if(!crossProduct)
        return 0;
    else
        return -1;
}

void input() {
    cin >> p1.fi >> p1.se >> p2.fi >> p2.se;
    cin >> p3.fi >> p3.se >> p4.fi >> p4.se;
    
    // CCW 구하기
    CCWres[0] = CCW(p1, p2, p3);
    CCWres[1] = CCW(p1, p2, p4);
    CCWres[2] = CCW(p3, p4, p1);
    CCWres[3] = CCW(p3, p4, p2);
}

bool LineSegmentIntersection() {
    if(CCWres[0]*CCWres[1] < 0 && CCWres[2]*CCWres[3] < 0)
        return true;
    if((!(CCWres[0]*CCWres[1]) && CCWres[2]*CCWres[3] < 0) || (CCWres[0]*CCWres[1] < 0 && !(CCWres[2]*CCWres[3])))
        return true;
    if(CCWres[0] || CCWres[1] || CCWres[2] || CCWres[3])
        if(!(CCWres[0]*CCWres[1]) && !(CCWres[2]*CCWres[3]))
            return true;
    if(!CCWres[0] && !CCWres[1] && !CCWres[2] && !CCWres[3]) {
        if(p2 > p4) {
            swap(p1, p3);
            swap(p2, p4);
        }
        if(p1 > p2)
            swap(p1, p2);
        if(p3 > p4)
            swap(p3, p4);
        
        if((p3 < p2 && p1 < p4) || (p1 < p4 && p2 == p3) || (p1 == p3 && p2 == p4))
            return true;
    }
    return false;
}

pdd GetIntersectionPoint() {
    double xs, xm, ys, ym;
    ll x1, y1, x2, y2, x3, y3, x4, y4;
    x1 = p1.fi, y1 = p1.se;
    x2 = p2.fi, y2 = p2.se;
    x3 = p3.fi, y3 = p3.se;
    x4 = p4.fi, y4 = p4.se;
    
    xs = (x1*y2 - y1*x2) * (x3 - x4) - (x1 - x2) * (x3*y4 - y3*x4);
    xm = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    ys = (x1*y2 - y1*x2) * (y3 - y4) - (y1 - y2) * (x3*y4 - y3*x4);
    ym = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    
    if(!xm)
        return {INF, INF};
    return {xs/xm, ys/ym};
}

void print(pdd p) {
    if(p.fi == (int)p.fi && p.se == (int)p.se) {
        cout.precision(0);
        cout << p.fi << ' ' << p.se;
    }
    else {
        cout.precision(16);
        cout << p.fi << ' ' << p.se;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    cout << (res = LineSegmentIntersection()) << '\n';
    
    if(res) {
        cout << fixed;
        resp = GetIntersectionPoint();
        if((int)resp.fi != INF || (int)resp.se != INF)
            print(resp);
        else if(p1 < p4 && p2 == p3)
            print(p2);
    }
    
    return 0;
}

 

<선분의 교차 여부 - 1>

https://gaussian37.github.io/math-algorithm-line_intersection/

선분의 교차 여부 확인

 

<선분의 교차 여부 - 2>

https://jordano-jackson.tistory.com/27

[Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘

 

<두 선분의 교점>

https://gaussian37.github.io/math-algorithm-intersection_point/

두 선분(직선)의 교점

 

<외적>

https://namu.wiki/w/%EC%99%B8%EC%A0%81

외적 - 나무위키

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.