백준 17387 선분 교차2 [c++]

in Develop / Solving

c++

진짜 푸는 데 오열했다. 뭘 빼놓고 생각하고 있는지 계속 그려보면서 겨우 답을 찾았다.

문제 분석

  • 두 선분을 이루는 좌표 네 개가 주어진다.
  • 이 선분들이 교차하면 1, 아니면 0을 출력하여라.

입력조건

선분1의 좌표 x1 y1 x2 y2
선분2의 죄표 x3 y3 x4 y4

풀이과정

  • 두 점을 이용해서 직선을 구하고, 이 직선의 교점을 찾는 식으로 먼저 접근해 보았다.

  • 매개변수 표현법을 이용하여 접근하였으나, 소수의 표현부에서 실제 답과 차이가 나서 제대로 통과가 되지 않는 듯 했다.

  • 2시간 자고 일어나서(이때 새벽 6시였다. 뭐하자고 자기 전에 이런 문제를 봐버려가지고 잠도 못자고 이 난리를 쳤는지 모르겠다…) 코드를 다 지우고 다시 짜기 시작했다.
  • 새로운 코드는 외적을 이용하였다.
  • 두 선분이 교차하려면, 한 선분을 기준으로 다른 선분의 점이 각각 선분으로 나누어 져야 한다.
  • 이 때문에, 선분 벡터1과, 선분의 점 -> 다른 선분의 점 벡터2를 외적한 값이 하나는 양수, 하나는 음수가 나오게 된다.(정방향 회전, 역방향 회전)
  • 여기까지가 기본 개념으로, 이 외에 다양한 예외처리가 필요했다.
  • x좌표가 일정한 상황에는, y좌표를 이용하여 겹치는지를 비교하여햐 하며, 그 반대도 고려.
  • 선분이 교차하는 것으로 판단되지만 한쪽 선분이 짧아서 만나지 못하는 경우 등 다양한 조건의 고려가 필요했고, 이 조건을 맞추는 데에 많은 시간을 소모하였다.

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

struct coordinate {
    long long x;
    long long y;
};

bool comparecoordi(const coordinate p1, const coordinate p2) {
    if(p1.x != p2.x) return p1.x - p2.x;
    else             return p1.y - p2.y;
}

void partcal(long long px1, long long px2, long long px3, long long px4) {
    long long x1 = min(px1, px2);
    long long x2 = max(px1, px2);
    
    long long x3 = min(px3, px4);
    long long x4 = max(px3, px4);

    if(x2 >= x3 && x1 <= x4) cout << 1;
    else cout << 0; 
}


int externalproduct(coordinate std, coordinate p1, coordinate p2) {
    coordinate dir1, dir2;
    dir1.x = p1.x - std.x;
    dir1.y = p1.y - std.y;

    dir2.x = p2.x - std.x;
    dir2.y = p2.y - std.y;

    long long res = dir1.x * dir2.y - dir2.x * dir1.y;

    // long long res2 = std.x * p1.y + p1.x * p2.y + p2.x * std.y;
    // res2 -= std.y * p1.x + p1.y * p2.x + p2.y * std.x;
    // cout << res << " " << res2 << endl;

    if(res > 0) return 1;
    else if(res == 0) return 0;
    else return -1;
}

int main() {
    // 좌표 두 개 받아서 교차 판단.
    coordinate p1, p2, p3, p4;

    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    cin >> p3.x >> p3.y >> p4.x >> p4.y;
    // 입력 끝.

    // p1 -> p2를 기준으로 p3, p4를 외적.
    // p3 -> p4를 기준으로 p1, p2를 외적.
    
    // cout << externalproduct(p1, p2, p3) << " " << externalproduct(p1, p2, p4) << endl;
    // cout << externalproduct(p3, p4, p1) << " " << externalproduct(p3, p4, p2) << endl;

    int case1 = externalproduct(p1, p2, p3) * externalproduct(p1, p2, p4);
    int case2 = externalproduct(p3, p4, p1) * externalproduct(p3, p4, p2);

    if(case1 == 0 && case2 == 0) {
        // 값 비교 필요.
        if(p1.x != p2.x) partcal(p1.x, p2.x, p3.x, p4.x);
        else             partcal(p1.y, p2.y, p3.y, p4.y);
        return 0;
    }
    else if(case1 <= 0 && case2 <= 0) cout << 1;
    else cout << 0;
}

다른 사람들 코드를 보며 복잡해서 읽지 못하겠다고 생각했는데, 지금 보니 내 코드도 똑같다…