Untitled

mail@pastecode.io avatar
unknown
c_cpp
10 months ago
7.8 kB
3
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

struct Point {
    int x = 0, y = 0;

    Point(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

struct Vector {
    int x = 0, y = 0;

    Vector(int _x, int _y) {
        x = _x;
        y = _y;
    }

    Vector(Point a) {
        x = a.x;
        y = a.y;
    }

    Vector(Point a, Point b) {
        x = b.x - a.x;
        y = b.y - a.y;
    }

    Vector operator+(const Vector &other) {
        return {x + other.x, y + other.y};
    }

    Vector operator-(const Vector &other) {
        return {x - other.x, y - other.y};
    }

    int operator*(const Vector &other) {
        return x * other.x + y * other.y;
    }

    int operator^(const Vector &other) {
        return x * other.y - other.x * y;
    }
};

Point O(0, 0);

int dist2(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

double dist(Point a, Point b) {
    return sqrt(dist2(a, b));
}

int len2(Vector v) {
    return v.x * v.x + v.y * v.y;
}

double len(Vector v) {
    return sqrt(len2(v));
}

double dist_point_seg(Point a, Point c, Point d) {
    Vector CD(c, d), CA(c, a), DC(d, c), DA(d, a);
    if (CD * CA <= 0) {
        return dist(a, c);
    } else if (DC * DA <= 0) {
        return dist(a, d);
    } else {
        return abs(CA ^ CD) / len(CD);
    }
}

double dist_point_ray(Point a, Point c, Point d) {
    Vector CD(c, d), CA(c, a), DC(d, c), DA(d, a);
    if (CD * CA <= 0) {
        return dist(a, c);
    } else {
        return abs(CA ^ CD) / len(CD);
    }
}

double dist_point_line(Point a, Point c, Point d) {
    Vector CD(c, d), CA(c, a);
    return abs(CA ^ CD) / len(CD);
}

bool inter_seg_seg(Point a, Point b, Point c, Point d) {
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    if ((CA ^ CD) == 0 || (CB ^ CD) == 0 || (AC ^ AB) == 0 || (AD ^ AB) == 0) {
        bool f = false;
        if ((CA ^ CD) == 0) {
            f |= (AC * AD <= 0);
        }
        if ((CB ^ CD) == 0) {
            f |= (BC * BD <= 0);
        }
        if ((AC ^ AB) == 0) {
            f |= (CA * CB <= 0);
        }
        if ((AD ^ AB) == 0) {
            f |= (DA * DB <= 0);
        }
        return f;
    } else {
        if ((CA ^ CD) > 0) {
            if ((CB ^ CD) > 0) return false;
        } else {
            if ((CB ^ CD) < 0) return false;
        }
        if ((AC ^ AB) > 0) {
            if ((AD ^ AB) > 0) return false;
        } else {
            if ((AD ^ AB) < 0) return false;
        }
        return true;
    }
}

double dist_seg_seg(Point a, Point b, Point c, Point d) {
    if (inter_seg_seg(a, b, c, d)) return 0;
    return min({dist_point_seg(a, c, d), dist_point_seg(b, c, d), dist_point_seg(c, a, b), dist_point_seg(d, a, b)});
}

bool inter_seg_ray(Point a, Point b, Point c, Point d) {
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    if (inter_seg_seg(a, b, c, d)) return true;
    if ((CA ^ CD) == 0 || (CB ^ CD) == 0 || (AC ^ AB) == 0) {
        bool f = false;
        if ((CA ^ CD) == 0) {
            f |= (CD * CA >= 0);
        }
        if ((CB ^ CD) == 0) {
            f |= (CD * CB >= 0);
        }
        if ((AC ^ AB) == 0) {
            f |= (CA * CB <= 0);
        }
        return f;
    } else {
        if ((CA ^ CD) > 0) {
            if ((CB ^ CD) > 0) return false;
        } else {
            if ((CB ^ CD) < 0) return false;
        }
        return dist_point_seg(c, a, b) > dist_point_seg(d, a, b);
    }
}

double dist_seg_ray(Point a, Point b, Point c, Point d) {
    if (inter_seg_ray(a, b, c, d)) return 0;
    return min({dist_point_seg(c, a, b), dist_point_ray(a, c, d), dist_point_ray(b, c, d)});
}

bool inter_seg_line(Point a, Point b, Point c, Point d) {
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    if ((CA ^ CD) == 0 || (CB ^ CD) == 0) return true;
    if ((CA ^ CD) > 0) {
        return (CB ^ CD) < 0;
    } else {
        return (CB ^ CD) > 0;
    }
}

double dist_seg_line(Point a, Point b, Point c, Point d) {
    if (inter_seg_line(a, b, c, d)) return 0;
    return min(dist_point_line(a, c, d), dist_point_line(b, c, d));
}

bool inter_line_line(Point a, Point b, Point c, Point d) {
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    int ka1 = -AB.y, kb1 = AB.x, ka2 = -CD.y, kb2 = CD.x;
    return kb2 * ka1 - ka2 * kb1 != 0;
}

double dist_line_line(Point a, Point b, Point c, Point d) {
    if (inter_line_line(a, b, c, d)) return 0;
    return dist_point_line(a, c, d);
}

bool inter_ray_ray(Point a, Point b, Point c, Point d) { // ???
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    if (!inter_line_line(a, b, c, d)) return false;
    if (inter_seg_ray(a, b, c, d) || inter_seg_ray(c, d, a, b)) return true;
    Vector OC(O, c);
    Vector CB1 = OC + AB;
    if ((CA ^ CD) == 0) {
        return CA * CD >= 0;
    }
    if ((CA ^ CD) > 0) {
        return (CB1 ^ CD) < 0;
    } else {
        return (CB1 ^ CD) > 0;
    }
}

double dist_ray_ray(Point a, Point b, Point c, Point d) {
    if (inter_ray_ray(a, b, c, d)) return 0;
    return min(dist_point_ray(a, c, d), dist_point_ray(c, a, b));
}

bool inter_ray_line(Point a, Point b, Point c, Point d) {
    if (!inter_line_line(a, b, c, d)) return false;
    return inter_ray_ray(a, b, c, d) || inter_ray_ray(a, b, d, c);
}

double dist_ray_line(Point a, Point b, Point c, Point d) {
    Vector AB(a, b), AC(a, c), AD(a, d), BA(b, a), BC(b, c), BD(b, d), CA(c, a), CB(c, b), CD(c, d), DA(d, a), DB(d, b), DC(d, c);
    if (inter_ray_line(a, b, c, d)) return 0;
    return dist_point_line(a, c, d);
}

void solve() {
    cout.precision(10);
    cout << fixed;

    double xa, ya, xb, yb, xc, yc, xd, yd;
    cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;

    Point A(xa, ya), B(xb, yb), C(xc, yc), D(xd, yd);
    Vector AB(A, B), AC(A, C), AD(A, D), BA(B, A), BC(B, C), BD(B, D), CA(C, A), CB(C, B), CD(C, D), DA(D, A), DB(D, B), DC(D, C);

    // 1
    cout << dist(A, C) << '\n';

    // 2
    cout << dist_point_seg(A, C, D) << '\n';
    
    // 3
    cout << dist_point_ray(A, C, D) << '\n';

    // 4
    cout << dist_point_line(A, C, D) << '\n';

    // 5
    cout << dist_point_seg(C, A, B) << '\n';

    // 6
    cout << dist_seg_seg(A, B, C, D) << '\n';

    // 7
    cout << dist_seg_ray(A, B, C, D) << '\n';

    // 8
    cout << dist_seg_line(A, B, C, D) << '\n';

    // 9
    cout << dist_point_ray(C, A, B) << '\n';

    // 10
    cout << dist_seg_ray(C, D, A, B) << '\n';

    // 11
    cout << dist_ray_ray(A, B, C, D) << '\n';

    // 12
    cout << dist_ray_line(A, B, C, D) << '\n';

    // 13
    cout << dist_point_line(C, A, B) << '\n';

    // 14
    cout << dist_seg_line(C, D, A, B) << '\n';

    // 15
    cout << dist_ray_line(C, D, A, B) << '\n';

    // 16
    cout << dist_line_line(A, B, C, D) << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}