글 읽기 - 두 선분의 교차 여부

79brue 5년 전 1

두 선분의 교차 여부는 ccw를 이용해서 알아낼 수 있습니다.

그런데, 이 방법이 먹히지 않는 경우가 있더라고요. 두 선분의 기울기가 같은 경우입니다.

이 경우는 어떻게 처리를 해 주어야 하나요?

아래 코드는 두 선분이 교차하는지 판별하는데, 오류가 있는 것 같습니다.

double PI = 2.0 * acos(0.0);
struct vector2{
    ll x, y;
    explicit vector2(ll x_=0, ll y_=0): x(x_), y(y_){}

    bool operator==(const vector2 &r)const{
        return x == r.x && y == r.y;
    }
    bool operator<(const vector2 &r)const{
        return x != r.x ? x < r.x : y < r.y;
    }

    vector2 operator * (double r)const{
        return vector2(x*r, y*r);
    }

    vector2 operator +(const vector2 &r)const{
        return vector2(x+r.x, y+r.y);
    }
    vector2 operator -(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    double dist() const{
        return hypot(x, y);
    }

    double norm() const{
        return hypot(x, y);
    }

    vector2 normalize() const{
        return vector2(x/norm(), y/norm());
    }

    double polar() const{
        return fmod(atan2(y, x) + 2*PI, 2*PI);
    }

    ll dot(const vector2& r)const{
        return x*r.x + y*r.y;
    }
    ll cross(const vector2 &r)const{
        return x*r.y - y*r.x;
    }

    vector2 project(const vector2 &r)const{
        vector2 rv = r.normalize();
        return rv * r.dot(*this);
    }
}; // 알고리즘 문제해결전략 1권 참조

bool segmentIntersect(vector2 a, vector2 b, vector2 c, vector2 d){
    if(ccw(b-a, d-c) == 0){ // 평행인 경우
        if(a.x == b.x){
            if(a.x != c.x) return false;
            if(a.y > b.y) swap(a, b);
            if(c.y > d.y) swap(c, d);
            return (a.y <= d.y) ^ (b.y <= c.y);
        }
        if((a.x - b.x) * (c.y - b.y) != (a.y - b.y) * (c.x - b.x)){
            return false;
        }
        if(a.x > b.x) swap(a, b);
        if(c.x > d.x) swap(c, d);
        if((a.x <= d.x) ^ (b.x <= c.x)) return true;
        return false;
    }
    ll ab = ccw(a, b, c) * ccw(a, b, d);
    ll cd = ccw(c, d, a) * ccw(c, d, b);
    if(!ab && !cd){
        if(b<a) swap(a, b);
        if(d<c) swap(c, d);
        return !(b<c || d<a);
    }
    return ab<=0 && cd<=0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 선분의 교차 여부

79brue 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말