# 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;
}```