백준 No.17386 [선분 교차 1]

Baekjoon Online Judge No.17386 [선분 교차 1]

---

 문제 

17386번: 선분 교차 1

---

 설명 

  선분 교차 여부를 확인하기 위해서 CCW를 사용하였다.  

 

  CCW 설명 Link : 2021.06.27 - [C++ Algorithm/Math] - CCW (Counter Clock Wise)

 

 < 두 선분의 내부가 교차하는 경우 > 

  위 첨부된 사진을 보면 CCW(A, B, C) 의 값은 양수이고 CCW(A, B, D) 의 값은 음수이다. 또한 CCW(C, D, A) 의 값은 음수이고 CCW(C, D, B) 의 값은 양수이다. 두 선분이 교차를 하기 위해선 선분AB를 기준으로 점 C, 점 D 가 서로 반대편에 있으면서 선분CD를 기준으로 또한 점 A, 점 B 가 서로 반대편에 있어야 한다. 따라서 아래와 같은 공식에 성립해야 한다.

 

 CCW(A, B, C) * CCW(A, B, D) < 0    &&    CCW(C, D, A) * CCW(C, D, B) < 0

  위 경우에 성립을 하면, 점 C, D 는 선분AB의 연장선상 직선을 기준으로 항상 서로 반대편에 존재하고 점 A, B는 선분CD의 연장선상 직선을 기준으로 서로 반대편에 존재함으로써 교점이 존재하는 상태로 판단할 수 있다.

 

  이 문제는 조건에서 세 점이 일직선 위에 있는 경우는 없다고 하였으므로 위 경우만 고려하면 된다. 하지만 17387번: 선분 교차 2 (acmicpc.net) 문제 부턴 세 점이 일직선 위에 있는 경우 혹은 네 점 모두 한 직선 위에 있는 경우를 모두 고려하여야 한다. 이 경우들은 어떻게 고려할지 위 경우에서 그냥 간단하게 응용만 하면 된다.

 

  백준 No.17387 [선분 교차 2] 설명 Link : 2021.06.29 - [C++ Algorithm/Math] - 백준 No.17387 [선분 교차 2]

---

 Code 

#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
struct coordinate {
    LL x;
    LL y;
 
    void read() { cin >> x >> y; }
};
 
int CCW(coordinate A, coordinate B, coordinate C) {
    // temp 에 대한 연산을 나누는 이유 : 연산 과정에서 Overflow가 발생할 수 있으므로
    LL temp = (A.x * B.y) + (B.x * C.y) + (C.x * A.y);
    temp -= (A.x * C.y) + (B.x * A.y) + (C.x * B.y);
    
    // CCW의 값이 양수인지, 0 인지, 음수인지만 알면 되므로 아래와 같이 return 을 하였다.
    if (temp > 0) return 1;
    else if (!temp) return 0;
    else return - 1;
}
 
bool isOverlapped(coordinate A, coordinate B, coordinate C, coordinate D) {
    int ans1 = CCW(A, B, C) * CCW(A, B, D); // 선분AB를 기준으로 점 C, 점 D 를 체크하는 부분
    int ans2 = CCW(C, D, A) * CCW(C, D, B); // 선분CD를 기준으로 점 A, 점 B 를 체크하는 부분
 
    return (ans1 < 0) && (ans2 < 0); // 위에서 설명이 된 조건에 부합하면 1, 부합하지 않으면 0을 return
}
 
int main() {
    coordinate A, B, C, D;
 
    A.read(); B.read();
    C.read(); D.read();
 
    if (isOverlapped(A, B, C, D)) cout << "1";    // 겹치는 부분이 있다면 1을 출력
    else cout << "0";                            // 겹치는 부분이 없다면 0을 출력
}