Untitled
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; }