[백준/Baekjoon] 17386 선분 교차 1 C++ :: Geometry

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

17386번: 선분 교차 1

---

1. Logic

CCW알고리즘을 활용하여 풀이 가능하다.

CCW 알고리즘이란 임의의 선분을 기준으로 다른 한 점이 시계방향으로 위치하는지 반시계방향에 위치하는지 판별할 수 있는 알고리즘이다. 이 알고리즘은 수학시간에 했던 신발끈 공식, 외적을 생각하면 쉽게 이해할 수 있다.

한 선분(선분을 이루는 두 점 A, B)과 다른 한 점(C)을 외적한 값을 CCW(A, B, C)=outer라고 했을 때

outer > 0 : 다른 한 점이 시계방향에 위치

outer == 0 : 일직선에 위치

outer < : 다른 한 점이 반 시계방향에 위치

 

아래의 왼쪽 그림을 보면 CCW(a, b, c)는 음수이고, CCW(a, b, d)는 양수이다. 똑같이 CCW (c, d, a)는 음수 CCW (c, d, b)는 양수이다. 그래서 두개를 곱한 값이 둘다 양수이기 때문에 두 점의 위치는 반대이고 두 점을 이엇을 때 교차한다고 볼 수 있다. 

반대로 오른쪽 그림을 보면 CCW(a, b, c)는 음수 CCW(a, b, d)는 양수이기 때문에 두개의 외적값 곱은 음수이고  CCW(c, d, a)는 음수, CCW(c, d, b)도 음수이기 때문에 두개의 곱은 양수이다. 이경우 하나는 음수이고 하나는 양수이기 때문에 교차하지 않는다고 볼 수 있다. 이와 같이 CCW알고리즘을 사용하여 선분의 교차판정을 할 수 있다.

출처 : https://velog.io/@vkdldjvkdnj/boj02162

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int ccw(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c) {
    long long outer = a.first*b.second + b.first*c.second + c.first*a.second - 
                        (a.first*c.second + b.first*a.second + c.first*b.second);
                        
    if(outer > 0) return 1;
    else if(outer == 0) return 0;
    else if(outer < 0) return -1;
}

int main() {
    pair<long long, long long> a;
    pair<long long, long long> b;
    pair<long long, long long> c;
    pair<long long, long long> d;
    
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;
    cin >> c.first >> c.second;
    cin >> d.first >> d.second;
    
    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) {
        cout << 1;
    }
    else cout << 0;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐