[백준 20149] 선분 교차 3

20149번: 선분 교차 3

시간제한: 0.25초

메모리제한: 512MB

---

선분 교차의 3번째 문제이다. 경우를 나눠서 구현해야 하는 점이 쉽지 않다.

교차를 판정하거나 교차점을 구할 때 divide 0 에러가 발생하지 않도록 경우를 잘 나누자.

<소스 코드>

#include <cstdio>
int testequal(long long a, long long b, long long c, long long d) {
    if (a < b && c < d && a < d) {if (b == c) return 1;else return 4;}
    if (a < b && d < c && a < c) {if (b == d) return 1;else return 4;}
    if (b < a && c < d && b < d) {if (a == c) return 1;else return 4;}
    if (b < a && d < c && b < c) {if (a == d) return 1;else return 4;}
    if (c < d && a < b && c < b) {if (a == d) return 1;else return 4;}
    if (d < c && a < b && d < b) {if (a == c) return 1;else return 4;}
    if (c < d && b < a && c < a) {if (b == d) return 1;else return 4;}
    if (d < c && b < a && d < a) {if (b == c) return 1;else return 4;}
    return 0;
}
int isgyocha (long long x1,long long y1,long long x2,long long y2,long long x3,long long y3,long long x4,long long y4) {
    // 중간에 걸칠 때
    if ((((x3-x1)*(y2-y1) > (y3-y1)*(x2-x1) && (x4-x1)*(y2-y1) < (y4-y1)*(x2-x1))
    || ((x3-x1)*(y2-y1) < (y3-y1)*(x2-x1) && (x4-x1)*(y2-y1) > (y4-y1)*(x2-x1)))
    && (((x1-x3)*(y4-y3) > (y1-y3)*(x4-x3) && (x2-x3)*(y4-y3) < (y2-y3)*(x4-x3))
    || ((x1-x3)*(y4-y3) < (y1-y3)*(x4-x3) && (x2-x3)*(y4-y3) > (y2-y3)*(x4-x3)))) return 1;
    // 일직선
    else if ( ((x3-x1)*(y2-y1) == (y3-y1)*(x2-x1) && (x4-x1)*(y2-y1) == (y4-y1)*(x2-x1))
    && ((x1-x3)*(y4-y3) == (y1-y3)*(x4-x3) && (x2-x3)*(y4-y3) == (y2-y3)*(x4-x3)) ) {
        if ((x1 < x2 && x2 < x3 && x3 < x4) || (x1 < x2 && x2 < x4 && x4 < x3) ||
            (x2 < x1 && x1 < x3 && x3 < x4) || (x2 < x1 && x1 < x4 && x4 < x3) ||
            (x3 < x4 && x4 < x1 && x1 < x2) || (x3 < x4 && x4 < x2 && x2 < x1) ||
            (x4 < x3 && x3 < x1 && x1 < x2) || (x4 < x3 && x3 < x2 && x2 < x1) ||
            (y1 < y2 && y2 < y3 && y3 < y4) || (y1 < y2 && y2 < y4 && y4 < y3) ||
            (y2 < y1 && y1 < y3 && y3 < y4) || (y2 < y1 && y1 < y4 && y4 < y3) ||
            (y3 < y4 && y4 < y1 && y1 < y2) || (y3 < y4 && y4 < y2 && y2 < y1) ||
            (y4 < y3 && y3 < y1 && y1 < y2) || (y4 < y3 && y3 < y2 && y2 < y1)) return 0;
        else if (testequal(x1,x2,x3,x4) != 0) return testequal(x1,x2,x3,x4);
        else if (testequal(y1,y2,y3,y4) != 0) return testequal(y1,y2,y3,y4);
        else return 0;
    }
    // 한 점 위에 있을 때
    else if ((((x3-x1)*(y2-y1) >= (y3-y1)*(x2-x1) && (x4-x1)*(y2-y1) <= (y4-y1)*(x2-x1)) 
    || ((x3-x1)*(y2-y1) <= (y3-y1)*(x2-x1) && (x4-x1)*(y2-y1) >= (y4-y1)*(x2-x1)))
    && (((x1-x3)*(y4-y3) >= (y1-y3)*(x4-x3) && (x2-x3)*(y4-y3) <= (y2-y3)*(x4-x3))
    || ((x1-x3)*(y4-y3) <= (y1-y3)*(x4-x3) && (x2-x3)*(y4-y3) >= (y2-y3)*(x4-x3)))) return 1;
    else return 0;
}
int main() {
    long long x1,y1,x2,y2,x3,y3,x4,y4;
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
    int result = isgyocha(x1, y1, x2, y2, x3, y3, x4, y4);
    if (result == 0) printf("0");
    else if (result == 4) printf("1");
    else {
        printf("1\n");
        double gyox, gyoy, m1, m2, n1, n2;
        if (x1 == x2 && x3 == x4) {
            if (y1 == y3 || y1 == y4) printf("%lld %lld", x1, y1);
            else if (y2 == y3 || y2 == y4) printf("%lld %lld", x1, y2);
        }
        else if (x1 == x2) {
            gyox = double(x1);
            m2 = double(y4-y3)/double(x4-x3);
            gyoy = m2*gyox+(y3-m2*x3);
            printf("%.15lf %.15lf", gyox, gyoy);
        }
        else if (x3 == x4) {
            gyox = double(x3);
            m1 = double(y2-y1)/double(x2-x1);
            gyoy = m1*gyox+(y1-m1*x1);
            printf("%.15lf %.15lf", gyox, gyoy);
        }
        else {
            m1 = double(y2-y1)/double(x2-x1);
            m2 = double(y4-y3)/double(x4-x3);
            if (m1 == m2) {
                if ((x1 == x3 && y1 == y3)||(x1 == x4 && y1 == y4)) printf("%lld %lld", x1, y1);
                else if ((x2 == x3 && y2 == y3)||(x2 == x4 && y2 == y4)) printf("%lld %lld", x2, y2);
            }
            else {
                n1 = y1-m1*x1; n2 = y3-m2*x3;
                gyox = (n2-n1)/(m1-m2);
                gyoy = m1*gyox+n1;
                printf("%.15lf %.15lf", gyox, gyoy);
            }
        }
    }
}

<코드 설명>

$isgyocha()$ 함수는 0, 1, 4를 리턴할 수 있는데,

0은 교차점이 없을 때

1은 교차점이 하나일 때

4는 교차점이 무수히 많을 때이다.

$isgyocha()$ 함수에서,

1) 중간에 걸칠 때

이런 경우로, 무조건 1을 리턴한다.

2) 일직선에 있을 때

0을 리턴

1을 리턴

4를 리턴

이렇게 3가지 경우로 나뉜다.

3) 한 점 위에 있을 때

이런 경우로, 무조건 1을 리턴한다.