백준[20149] 선분 교차 3

문제 설명

풀이

이 문제는 선행 문제인 선분교차 2 이 문제를 풀었다면 어렵지 않다. 이 문제를 모른다면 여기를 참고하자.

위의 문제를 이해했다고 가정하고 설명하겠다. 이 문제는 선분 교차 2에서 교점의 좌표만 추가로 구하면 된다. 교점의 좌표는 두 점으로부터 직선의 방정식 두 개를 구한 후 연립하면 된다. 이때 직선이 y축과 평행할 때를 조심해야 한다. 나는 이 것을 간과해 맞왜틀을 외치다 질문검색을 들어가 봤다.

코드

#include <cstdio>
#include <algorithm>
#define x first
#define y second

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll ccw(pll a, pll b, pll c) {
    ll ret = a.x * b.y + b.x * c.y + c.x * a.y;
    ret = ret - (b.x * a.y + c.x * b.y + a.x * c.y);
    if (ret > 0) return 1;
    else if (ret < 0) return -1;
    else return 0;
}

bool check(pll a, pll b, pll c, pll d) { // 선분이 겹치는지 여부
    ll abc = ccw(a, b, c), abd = ccw(a, b, d);
    ll cda = ccw(c, d, a), cdb = ccw(c, d, b);
    if (abc * abd == 0 && cda * cdb == 0) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return a <= d && c <= b;
    } else {
        return abc * abd <= 0 && cda * cdb <= 0;
    }
}

int main() {
    pll a, b; scanf("%lld %lld %lld %lld", &a.x, &a.y, &b.x, &b.y);
    pll c, d; scanf("%lld %lld %lld %lld", &c.x, &c.y, &d.x, &d.y);
    if (check(a, b, c, d)) {
        printf("1\n");
        //한점에서 만나는 경우
        if (a >= b) swap(a, b);
        if (c >= d) swap(c, d);
        if (b == c) {
            printf("%lld %lld", b.x, b.y);
            return 0;
        } else if (a == d) {
            printf("%lld %lld", a.x, a.y);               
            return 0;
        }

        // 나누는 수가 0이 아닌 경우
        if (a.x != b.x && c.x != d.x) {
            double f1[3], f2[3];
            f1[0] = double(a.y - b.y) / double(a.x - b.x);
            f1[1] = -1;
            f1[2] = double(a.y - b.y) / double(a.x - b.x) * a.x * -1 + a.y;
            f2[0] = double(c.y - d.y) / double(c.x - d.x);
            f2[1] = -1;
            f2[2] = double(c.y - d.y) / double(c.x - d.x) * c.x * -1 + c.y;        
            if (f1[0] == f2[0]) {
                return 0;
            }
            double x1 = (f1[2] - f2[2]) / (f1[0] - f2[0]) * -1;
            double y1 = f1[0] * x1 + f1[2];
            printf("%.9lf %.9lf", x1, y1);
        // 나누는 수가 0인 경우 
        // ex) x = 2와 같은 y축과 평행한 직선이 존재하는 경우
        } else {
            if (a.x == b.x) {
                double f2[3];
                f2[0] = double(c.y - d.y) / double(c.x - d.x);
                f2[1] = -1;
                f2[2] = double(c.y - d.y) / double(c.x - d.x) * c.x * -1 + c.y;
                printf("%lld %.9lf", a.x, f2[0] * double(a.x) + f2[2]);
            }
            else {
                double f1[3];
                f1[0] = double(a.y - b.y) / double(a.x - b.x);
                f1[1] = -1;
                f1[2] = double(a.y - b.y) / double(a.x - b.x) * a.x * -1 + a.y;
                printf("%lld %.9lf", c.x, f1[0] * double(c.x) + f1[2]);
            }

        }
    } else {
        printf("0");
    }
}