백준 No.17387 [선분 교차 2]

Baekjoon Online Judge No.17387 [선분 교차 2]

---

 문제 

17387번: 선분 교차 2

---

 설명 

  이전 17386번: 선분 교차 1 (acmicpc.net) 문제에서 조건이 더 추가가 된 문제이다. [선분 교차 1] 문제에선 세 점이 한 직선상에 있는 경우가 없었지만, 이번 문제에선 세 점이 한 직선상에 있는 경우가 있기에 이 조건까지 처리를 해야 한다. 이전에 올린 [선분 교차 1] 게시물에서 더 추가해야 하는 조건을 설명 해 보고자 한다.

 

  백준 No.17386 [선분 교차 1] 설명 Link : 2021.06.28 - [C++ Algorithm/Math] - 백준 No.17386 [선분 교차 1]

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

---

  [선분 교차 1] 에선 두 선분의 내부끼리 교차하는 경우만을 고려하였다. 하지만 이번 문제에선 세 점이 한 직선상에 있는 경우와 네 점 모두 한 직선상에 있는 경우를 고려해야 한다.

 

<세 점이 한 직선상에 있는 경우>

  세 점이 한 직선상에 있는 경우는 위 세 가지 경우로 나뉜다. 

 

  Case 1) CCW(A, B, C) * CCW(A, B, D) < 0   &&   CCW(C, D, A) * CCW(C, D, B) == 0
  Case 2) CCW(A, B, C) * CCW(A, B, D) == 0   &&   CCW(C, D, A) * CCW(C, D, B) == 0
  Case 3) CCW(A, B, C) * CCW(A, B, D) > 0   &&   CCW(C, D, A) * CCW(C, D, B) == 0

 

  Case 1, Case 2 는 교차 하는 경우이며 Case 3 은 교차하지 않는 경우이다. 위 세 Case 들로 아래와 같은 조건을 도출할 수 있다.

 

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

 

  이 조건을 확인 한다면, 두 선분의 내부끼리만 교차하는 경우와 세 점이 한 직선상에 있는 경우에 교차 여부를 확인할 수 있다.

 

---

<네 점이 한 직선상에 있는 경우>

  네 점이 한 직선상에 있는 경우는, 점들간의 거리로 확인을 하였다. 위와 같이 두 케이스만 고려하면 된다.

 

  Case 1) A--B 의 거리보다 A--C,   A--D 의 거리가 더 멀어서 교차하지 않는 경우 -> 교차하지 않는다.
  Case 2) A--B 의 거리보다 A--C 혹은 A--D 의 거리가 더 짧은 경우 -> 교차한다.

 

  위 경우는 점 A 와 다른 세 점의 거리에 대해서 체크를 한 경우들이고 위와 같은 경우들을 점 B와 다른 세 점에 대해서만 한번 더 체크하면 된다.

---

 Code 

#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
struct coordinate {
    LL x;
    LL y;
 
    void read() { cin >> x >> y; }
};
 
// A---B---C 순서대로 한 직선에 나열이 되어 있는지 확인하는 함수
bool isLined(coordinate A, coordinate B, coordinate C) {
    if (A.x < B.x) {
        return B.x < C.x;
    }
    else if (B.x < A.x) {
        return C.x < B.x;
    }
    else {
        if (A.y < B.y) {
            return B.y < C.y;
        }
        else if (B.y < A.y) {
            return C.y < B.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 를 체크하는 부분
 
    if (!ans1 && !ans2) {    // 네 점이 모두 같은 선 상에 있을 때
                            // A--B 의 거리보다 A--C, A--D의 거리가 더 멀거나
                            // B--A 의 거리보다 B--C, B--D의 거리가 더 멀면 교점이 없는 경우이므로 false를 return
        if ((isLined(A, B, C) && isLined(A, B, D)) || (isLined(B, A, C) && isLined(B, A, D))) return false;
        else return true;    // 그렇지 않은 경우는 겹치는 부분이 존재하는 경우이므로 true를 return
    }
    else 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";
    else cout << "0";
}