BOJ 20149 선분 교차 3

1 개요[ | ]

BOJ 20149 선분 교차 3
2 같이 보기[ | ]

3 C++[ | ]

#include <bits/stdc++.h>
using namespace std;
 
struct Point {
    long long x, y;
    bool operator<=(Point const &a) {
        if(x == a.x) {
            return y <= a.y;
        }
        return x <= a.x;
    }
    bool operator==(Point const &a) {
        return x==a.x && y==a.y;
    }
};
Point p1, p2, p3, p4;

int ccw(const Point &a, const Point &b, const Point &c) {
    long long res = (a.x*b.y + b.x*c.y + c.x*a.y) - (b.x*a.y + c.x*b.y + a.x*c.y);
    if(res > 0) return 1;
    if(res < 0) return -1;
    return 0;
}
 
bool intersect() {
    long long std1 = ccw(p1, p2, p3) * ccw(p1, p2, p4);
    long long std2 = ccw(p3, p4, p1) * ccw(p3, p4, p2);
    if(std1 <= 0 && std2 <= 0) {
        if(std1 == 0 && std2 == 0) {
            if(p2 <= p1) swap(p1, p2);
            if(p4 <= p3) swap(p3, p4);
            return p1 <= p4 && p3 <= p2;
        }
        return true;
    }
    return false;
}
 
void solve(){
    if(!intersect()) {
        cout << 0;
        return;
    }
    cout << 1;
    long long d = (p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x);
    if(d == 0) {
        if(p2 == p3) {
            cout << '\n' << p2.x << ' ' << p2.y;
            return;
        }
        if(p1 == p4) {
            cout << '\n' << p1.x << ' ' << p1.y;
            return;
        }
        return;
    }
    cout.precision(17);
    cout << '\n' << 1.0 * ((p1.x*p2.y-p1.y*p2.x)*(p3.x-p4.x)-(p1.x-p2.x)*(p3.x*p4.y-p3.y*p4.x)) / d;
    cout << ' '  << 1.0 * ((p1.x*p2.y-p1.y*p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x*p4.y-p3.y*p4.x)) / d;
}
 
int main(){
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    cin >> p4.x >> p4.y;
    solve();
}