백준 17387번 - 선분 교차 2

백준 17386번 - 선분 교차 2 문제에서 세 점이 한 직선상에 있는 경우를 포함한 문제이다. 앞에서 이용한 CCW 알고리즘을 활용하면 되지만 조건을 추가로 고려야해야해서 간단한 문제는 아니었다.

조건문 분기에서 자꾸만 에러가 발생해서 애를 먹었다… 실수한 포인트는 다음과 같다.

int로 하게 되면 CCW 계산 과정에서 overflow 가능성이 있어서 에러가 발생한다.
if (ccw2 ==0 && ccw3 == 0) 와 같이 4점 모두 일직선에 있는 경우 x좌표만 비교하면 안되고 y좌표도 비교해줘야 한다.
- 0 1 0 2 0 3 0 4 와 같은 반례가 있기 때문!!

#include <iostream>
#include <cmath>

using namespace std;

int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3){
    long long temp = (x2-x1)*(y3-y1);
    temp -= (y2-y1)*(x3-x1);
    if (temp > 0){
        return 1; // 반시계 방향
    } else if (temp < 0){
        return -1; // 시계 방향
    } else{
        return 0; // 일직선
    }
}

int main()
{
    long long x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    int ccw2 = ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4);
    int ccw3 = ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2);
    
    if (ccw2 <= 0 && ccw3 <= 0){
        if (ccw2 ==0 && ccw3 == 0){ // 4점 모두 일직선
            if ((max(x1, x2) < min(x3, x4)) || (max(x3, x4) < min(x1, x2))){
                cout << 0;
            } else if ((max(y1, y2) < min(y3, y4)) || (max(y3, y4) < min(y1, y2))) {
                cout << 0;
            } else{
                cout << 1;
            }
        } else{
            cout << 1;
        }
    } else{
        cout << 0;
    }
    
    return 0;
}

Comments: