[C++]백준 - 20149번 문제

20149번: 선분 교차 3 (acmicpc.net)

20149번: 선분 교차 3

 

20149번 : 선분 교차 3

---

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

 

입력

---

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

 

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

 

 

출력

---

L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다.

두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.

좌표의 절대/상대 오차는 10-9까지 허용한다.

 

 

 

---

 

생각해 볼 점

---

교차판정은 17387에서 사용한 코드를 그대로 쓸 것입니다.

 

교차점은 Double을 이용해 계산을 할 것인데, 주의해야할 사항이 있습니다.

 

y = ax + b (a = 기울기)

의 공식을 써서 계산할 때, 

 

double a = 기울기 값;

 

과 같은 형태로 기울기를 변수에 저장해서 다시 계산해서는 안됩니다.

 

부동 소수점 오차로 인해서 정말 작은 단위의 오차도 곱해지고 더해지면서 큰 오차로 변하게 됩니다.

 

절대 변수를 이용해서 중간 결과를 저장하지 마세요!

 

그러므로, 저희는 정수 형태의 변수들만 이용해서 계산할 것입니다.

 

물론, 결과값은 소수점 형태로 변하겠지만, 한번에 계산하여 오차를 최대한 줄일 것입니다.

 

두 직선의 방정식은 다음과 같이 나타낼 수 있습니다.

 

Y - y1 =  a1(X - x1)

Y - y3 = a2(X - x3) 

 

이 방정식 두개를 이용해 X의 값을 구하면

 

(a1 - a2)X = y3 - y1 + a1 * x1 - a2 * x3

X = (y3 - y1 + a1x1 - a2x3) / (a1 - a2)
X = {(y3 - y1)(x2 - x1)(x4 - x3) + x1(y2 - y1)(x4 - x3) - x3(y4 - y3)(x2 - x1)} / {(y2 - y1)(x4 - x3) - (y4 - y3)(x2 - x1)}

 

위와 같이 정리됩니다.

이 식을 다시 방정식에 대입하면 Y의 값의 식 또한 도출할 수 있습니다.

 

이를 그대로 코드에 적어서 답을 도출하면 정답입니다.

 

코드

---

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Point;
#define swap(A, B) {Point temp; temp = A; A = B; B = temp;}


//두 직선 방정식을 구한 후, 교차점을 구함
void get_point(Point P1, Point P2, Point P3, Point P4)
{
    //y - y1 = a1(x - x1)
    //y - y3 = a2(x - x3)
    //y1 - y3 = a1x1 - a1x + a2x - a2x3
    //(a1 - a2)x = y3 - y1 + a1x1 - a2x3
    //x = (y3 - y1 + a1x1 - a2x3) / (a1 - a2) - > 정리하면
    //x = {(y3 - y1)(x2 - x1)(x4 - x3) + x1(y2 - y1)(x4 - x3) - x3(y4 - y3)(x2 - x1)} / {(y2 - y1)(x4 - x3) - (y4 - y3)(x2 - x1)}

    //y = (a1y3 - a1a2x3 + a1a2x1 - a2y1)/ (a1 - a2) -> 정리하면
    //y = {(y2 - y1)(y4 - y3)(x1 - x3) + y3(x4 - x3)(y2 - y1) - y1(x2 - x1)(y4 - y3)} / {(y2 - y1)(x4 - x3) - (y4 - y3)(x2 - x1)}

   

    //공통 분모, 만약 0일 경우 평행임
    double P = (P2.second - P1.second) * (P4.first - P3.first) - (P4.second - P3.second) * (P2.first - P1.first);


    //평행인 경우
    if (P == 0)
    {
        if (P2 < P1) swap(P1, P2);
        if (P4 < P3) swap(P3, P4);
        if (P1 == P4) cout << P1.first << " " << P1.second;
        else if(P2 == P3) cout << P2.first << " " << P2.second;
        return;
    }
    

    double X = ((P3.second - P1.second) * (P2.first - P1.first) * (P4.first - P3.first) +
                P1.first * (P2.second - P1.second) * (P4.first - P3.first) -
                P3.first * (P4.second - P3.second) * (P2.first - P1.first)) / P;
    double Y = ((P2.second - P1.second) * (P4.second - P3.second) * (P1.first - P3.first) +
                P3.second * (P4.first - P3.first) * (P2.second - P1.second) -
                P1.second * (P2.first - P1.first) * (P4.second - P3.second)) / P;

    cout << fixed; 
    cout.precision(10);
    cout << X << " " <<  Y;
}

//CCW 알고리즘
int ccw(Point A, Point B, Point C)
{
    ll temp1 = A.first * B.second + B.first * C.second + C.first * A.second;
    ll temp2 = A.second * B.first + B.second * C.first + C.second * A.first;
    ll result = temp1 - temp2;

    if (result < 0) return -1;
    else if (result == 0) return 0;
    else return 1;
}

//판정
bool is_crossed(Point P1, Point P2, Point P3, Point P4)
{
    int ccw1 = ccw(P1, P2, P3);
    int ccw2 = ccw(P2, P3, P4);
    int ccw3 = ccw(P3, P4, P1);
    int ccw4 = ccw(P4, P1, P2);

    bool is_crossed;

    //직선일 때
    if (ccw1 * ccw4 == 0 && ccw2 * ccw3 == 0)
    {
        if (P2 < P1) swap(P1, P2);
        if (P4 < P3) swap(P3, P4);

        //겹쳤으면
        if (P1 <= P4 && P3 <= P2) return true;
        else return false;
    }

    return ccw1 * ccw4 <= 0 && ccw2 * ccw3 <= 0;
}

int main()
{
    Point P1, P2, P3, P4;

    cin >> P1.first >> P1.second >> P2.first >> P2.second;
    cin >> P3.first >> P3.second >> P4.first >> P4.second;

    if (is_crossed(P1, P2, P3, P4))
    {
        cout << 1 << "\n";
        get_point(P1, P2, P3, P4);
    }
    else cout << 0;

    return 0;
}

 

그 외

---

식이 너무 길어서 전개하다가 비명횡사 할 뻔 했습니다...