[C++] 백준 11738 - 선분 교차 1(ccw, 계산 기하)

0. [c++] 백준  -

https://www.acmicpc.net/problem/11738

1. 풀이

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
 
 
using namespace std;
 
const double PI = 2.0 * acos(0.0);
const double EPSILON = 1e-9;
 
struct vector2
{
    double x, y;
    explicit vector2(double x_, double y_) :x(x_), y(y_) {}
    bool operator == (const vector2& rhs) const {
        return (x == rhs.x && y == rhs.y);
    }
    bool operator < (const vector2& rhs) const {
        return (x != rhs.x ? x < rhs.x : y < rhs.y);
    }
    vector2 operator + (const vector2& rhs) const {
        return vector2(x + rhs.x, y + rhs.y);
    }
    vector2 operator - (const vector2& rhs) const {
        return vector2(x - rhs.x, y - rhs.y);
    }
    vector2 operator * (double rhs) const {
        return vector2(x * rhs, y * rhs);
    }
 
    //벡터의 길이를 반환한다.
    double norm() const { return hypot(x, y); }
    //방향이 같은 단위 벡터를 반환한다.
    vector2 normalize() const {
        return vector2(x / norm(), y / norm());
    }
    //x축의 양의 방향으로부터 이 벡터까지의 반시계방향으로 잰 각도
    double polar() const { return fmod(atan2(y, x) + 2 * PI, 2 * PI); }
    //내적,외적의 구현
    double dot(const vector2& rhs) const {
        return  x * rhs.x + y * rhs.y;
    }
    double cross(const vector2& rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    //이 벡터를 rhs에 사영한 결과
    vector2 project(const vector2& rhs) const {
        vector2 r = rhs.normalize();
        return r * r.dot(*this);
    }
 
};
 
//++문제에 따라 추가해야 할 함수
 
//double형의 실수형 오류 방지
bool relativeEqual(double a, double b) {
    double diff = fabs(a - b);
    if (diff < 1e-10)return true;
    return diff <= 1e-8 * max(fabs(a), fabs(b));
}
 
//두 벡터의 사이각(세타)
double Interval(vector2 a, vector2 b) {
    return acos(a.dot(b) / a.norm() * b.norm());
}
 
//단순 다각형 p의 넓이를 구한다.
double area(const vector<vector2>& p) {
    double ret = 0;
    for (int i = 0; i < p.size(); i++)
    {
        int j = (i + 1) % p.size();
        ret += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return fabs(ret) / 2.0;
}
 
//3개의 점에서 a가 b보다 얼마나 p에 가까운지 반환하는 함수
double howMuchCloser(vector2 p, vector2 a, vector2 b) {
    return (b - p).norm() - (a - p).norm();
}
 
//위의 과정을 2개의 실수를 활용해 표현하는 방법
double howMuchCloser22(double px, double py, double ax, double ay, double bx, double by) {
    return sqrt((bx - px) * (bx - px) + (by - py) * (by - py)) - sqrt((ax - px) * (ax - px) + (ay - py) * (ay - py));
}
 
 
 
//코드 15.2 두 벡터의 방향성을 판단하는 ccw() 함수의 구현
 
//원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
//평행이면 0을 반환한다.
double ccw(vector2 a, vector2 b) {
    return a.cross(b);
}
 
//점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
//평행이면 0을 반환한다.
double ccw(vector2 p, vector2 a, vector2 b) {
    return ccw(a - p, b - p);
}
 
 
 
 
//코드 15.3 두 직선의 교차점을 계산하는 linelntersection() 함수의 구현
 
//(a,b)를 포함하는 선과 (c,d)를 포함하는 선의 교점을 x에 반환한다.
//두 선이 평행이면 (겹치는 경우를 포함) 거짓을, 아니면 참을 반환한다.
bool lineIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x) {
    double det = (b - a).cross(d - c);
    //두 선이 평행인 경우
    if (fabs(det) < EPSILON) return false;
    x = a + (b - a) * ((c - a).cross(d - c) / det);
    return true;
}
 
 
 
//코드 15.4 선분과 선분의 교차점을 계산하는 segmentlntersection()의 구현
 
//(a,b)와 (c,d)가 평행한 두 선분일 때 이들이 한 점에서 겹치는지 확인한다.
bool parallelSegments(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) {
    if (b < a) swap(a, b);
    if (d < c) swap(c, d);
    //한 직선 위에 없거나 두 선분이 겹치지 않는 경우를 우선 걸러낸다.
    if (ccw(a, b, c) != 0 || b < c || d < a) return false;
    //두 선분은 확실히 겹친다. 교차점을 하나 찾자.
    if (a < c) p = c; else p = a;
    return true;
}
//p가 (a,b)를 감싸면서 각 변이 x,y 축에 평행한 최소 사각형 내부에 있는지 확인한다.
//a,b,p는 일직선 상에 있다고 가정한다.
bool inBoundingRectangle(vector2 p, vector2 a, vector2 b) {
    if (b < a) swap(a, b);
    return p == a || p == b || (p < a&& p < b);
}
//(a,b) 선분과 (c,d) 선분의 교점을 p에 반환한다.
//교점이 여러 개일 경우 아무 점이나 반환한다.
//두 선분이 교차하지 않을 경우 false를 반환한다.
bool segmentIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) {
    //두 직선이 평행인 경우를 우선 예외로 처리한다.
    if (!lineIntersection(a, b, c, d, p))
        return parallelSegments(a, b, c, d, p);
    //p가 두 선분에 포함되어 있는 경우에만 참을 반환한다.
    return inBoundingRectangle(p, a, b) && inBoundingRectangle(p, c, d);
}
 
 
 
 
//15.5 두 선분의 교차 여부를 좀더 간단하게 확인하는 segmentIntersects() 함수의 구현
 
//두 선분이 서로 접촉하는지 여부를 반환한다.
bool segmentsIntersectects(vector2 a, vector2 b, vector2 c, vector2 d) {
    double ab = ccw(a, b, c) * ccw(a, b, d);
    double cd = ccw(c, d, a) * ccw(c, d, b);
    //두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우
    if (ab == 0 && cd == 0) {
        if (b < a) swap(a, b);
        if (d < c) swap(c, d);
        return !(b < c || d < a);
    }
    return ab <= 0 && cd <= 0;
}
 
int main() {
 
    double x, y;
    cin >> x >> y;
    vector2 a(x, y);
    cin >> x >> y;
    vector2 b(x, y);
    cin >> x >> y;
    vector2 c(x, y);
    cin >> x >> y;
    vector2 d(x, y);
 
    vector2 xx(x, y);
 
    if (segmentsIntersectects(a, b,c,d))
        cout << 1;
    else
        cout << 0;
 
    return 0;
}

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.517~537.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!