Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ld = long double;
- const ld eps = 1e-8;
- int equal(ld a, ld b) {
- return fabs(a - b) < eps;
- }
- struct point {
- ld x, y;
- point(ld a = 0, ld b = 0) :x(a), y(b) {}
- ld len() {
- return sqrt(x*x + y*y);
- }
- };
- bool operator == (point a, point b) {
- return equal(a.x, b.x) && equal(a.y, b.y);
- }
- ld operator * (point a, point b) { return a.x * b.y - b.x * a.y; }
- ld operator ^ (point a, point b) {
- return a.x * b.x + a.y * b.y;
- }
- point operator - (point a, point b) { return point(a.x - b.x, a.y - b.y); }
- struct line {
- ld a, b, c;
- point ff, ss;
- line(ld A = 0, ld B = 0, ld C = 0) : a(A), b(B), c(C) {}
- line(point f, point s) : a(f.y - s.y), b(s.x - f.x), c(f * s), ff(f), ss(s) {}
- bool lay(point a) {
- return equal(a.x*a + a.y*b + c, 0.0);
- }
- };
- int n;
- vector <point> a;
- point get_point(line b) {
- point f;
- if (b.b == 0) {
- f.x = -b.c / b.a;
- f.y = 0;
- }
- else {
- f.x = 0;
- f.y = -b.c / b.b;
- }
- return f;
- }
- point mid(point a, point b) {
- return point((a.x + b.x) / 2, (a.y + b.y) / 2);
- }
- bool cross(line a, line b, point &pt) {
- ld zn = point(a.a, a.b) * point(b.a, b.b);
- if (equal(zn, 0.0)) {
- auto f = get_point(b);
- if (a.lay(f)) {
- pt = f;
- return 1;
- }
- return 0;
- }
- pt.x = -(point(a.c, a.b) * point(b.c, b.b)) / zn;
- pt.y = -(point(a.a, a.c) * point(b.a, b.c)) / zn;
- return 1;
- }
- pair<point, ld> get_circle(point a, point b, point c) {
- line f(a, b);
- line s(b, c);
- line x(mid(a, b), mid(a, b) - point(f.a, f.b));
- line y(mid(b, c), mid(b, c) - point(s.a, s.b));
- point pt;
- cross(x, y, pt);
- return make_pair(pt, (pt - a).len());
- }
- bool cmp(point a, point b) {
- if ((a * b) != 0) {
- return (a * b) > 0;
- }
- return a.len() < b.len();
- }
- vector<point> convex_hull(vector <point> &a) {
- int j = -1;
- for (int i = 0; i < a.size(); ++i) {
- if (j == -1 || (a[i].y < a[j].y || (a[i].y == a[j].y && a[i].x < a[j].x)))
- j = i;
- }
- auto fx = a[j];
- for (int i = 0; i < a.size(); ++i) {
- a[i] = a[i] - fx;
- }
- rotate(a.begin(), a.begin() + j, a.end());
- sort(a.begin() + 1, a.end(), cmp);
- vector<point> hull;
- hull.push_back(a[0]);
- for (int i = 1; i < a.size(); ++i) {
- while (hull.size() > 1) {
- auto p1 = a[i] - hull.back();
- auto p2 = hull.back() - hull[hull.size() - 2];
- if (p2 * p1 > 0) break;
- hull.pop_back();
- }
- hull.push_back(a[i]);
- }
- fx.x *= -1;
- fx.y *= -1;
- for (auto &i : hull) {
- i = i - fx;
- }
- return hull;
- }
- ld dist(line a, point b) {
- if (a.ff == a.ss) return (a.ff - b).len();
- return fabs(a.a * b.x + a.b * b.y + a.c) / sqrt(a.a * a.a + a.b * a.b);
- }
- ld dist(line a, line b) {
- if (a.ff == a.ss && b.ff == b.ss) return (a.ff - b.ff).len();
- if (a.ff == a.ss) return dist(b, a.ff);
- if (b.ff == b.ss) return dist(a, b.ff);
- point pt;
- if (cross(a, b, pt)) return 0;
- return dist(a, get_point(b));
- }
- bool insight_seg(point a, point b, point c) {
- return equal((b - a) * (c - a), 0) && ((a - c) ^ (b - c)) <= 0;
- }
- bool insight_ray(point a, point b, point c) {
- ld F = ((b - a) ^ (c - a));
- return equal((b - a)*(c - a), 0) && ((b - a) ^ (c - a)) >= 0;
- }
- ld dist_to_seg(point a, point b, point c) { // отрезок ab
- if (a == b) return (a - c).len();
- ld A = (c - a).len();
- ld B = (c - b).len();
- ld C = (a - b).len();
- if (C*C + A*A > B*B && B*B + C*C > A*A) {
- return dist(line(a, b), c);
- }
- return min(A, B);
- }
- void norm(point &a) {
- ld h = sqrt(a.x * a.x + a.y*a.y);
- a.x /= h;
- a.y /= h;
- }
- point operator * (point a, ld k) { return point(a.x * k, a.y * k); }
- point operator + (point a, point b) { return point(a.x + b.x, a.y + b.y); }
- point projection(point a, line b) {
- point n(b.a, b.b);
- norm(n);
- ld k = dist(b, a);
- auto t1 = a, t2 = a;
- t1 = t1 - n * k, t2 = t2 + n * k;
- if (dist(b, t1) > dist(b, t2)) swap(t1, t2);
- return t1;
- }
- ld dist_to_ray(point a, point b, point c) { // луч ab
- if (a == b) return (a - c).len();
- auto v = projection(c, line(a, b));
- if (insight_ray(a, b, v)) {
- return dist(line(a, b), c);
- }
- return min((c - a).len(), (c - b).len());
- }
- bool cross_seg_with_seg(point a, point b, point c, point d) {
- point pt;
- bool t = cross(line(a, b), line(c, d), pt);
- if (t == 0) return 0;
- return insight_seg(a, b, pt) && insight_seg(c, d, pt);
- }
- ld dist_seg_to_seg(point a, point b, point c, point d) {
- if (a == b && c == d) return (a - c).len();
- if (a == b) return dist_to_seg(c, d, a);
- if (c == d) return dist_to_seg(a, b, c);
- if (cross_seg_with_seg(a, b, c, d)) return 0;
- return min(min(dist_to_seg(a, b, c), dist_to_seg(a, b, d)), min(dist_to_seg(c, d, a), dist_to_seg(c, d, b)));
- }
- bool cross_seg_with_ray(point a, point b, point c, point d) {
- point pt;
- bool t = cross(line(a, b), line(c, d), pt);
- if (t == 0) return 0;
- return insight_seg(a, b, pt) && insight_ray(c, d, pt);
- }
- ld dist_seg_to_ray(point a, point b, point c, point d) {
- if (a == b&& c == d) return (a - c).len();
- if (a == b) return dist_to_ray(c, d, a);
- if (c == d) return dist_to_ray(a, b, c);
- if (cross_seg_with_ray(a, b, c, d)) return 0;
- return min(min(dist_to_ray(c, d, a), dist_to_ray(c, d, b)), min(dist_to_seg(a, b, c), dist_to_seg(a, b, d)));
- }
- bool cross_line_with_seg(point a, point b, line c) {
- point pt;
- bool t = cross(line(a, b), c, pt);
- if (!t) return 0;
- return insight_seg(a, b, pt);
- }
- ld dist_seg_to_line(point a, point b, line c) {
- if (a == b && c.ff == c.ss) return (a - c.ff).len();
- if (a == b) return dist(c, a);
- if (c.ff == c.ss) return dist_to_seg(a, b, c.ff);
- if (cross_line_with_seg(a, b, c)) return 0;
- return min(dist(c, a), dist(c, b));
- }
- bool cross_line_with_ray(point a, point b, line c) {
- point pt;
- bool t = cross(line(a, b), c, pt);
- if (!t) return 0;
- return insight_ray(a, b, pt);
- }
- ld dist_ray_to_line(point a, point b, line c) {
- if (a == b && c.ff == c.ss) return (a - c.ff).len();
- if (a == b) return dist(c, a);
- if (c.ff == c.ss) return dist_to_ray(a, b, c.ff);
- if (cross_line_with_ray(a, b, c)) return 0;
- return min(dist(c, a), dist(c, b));
- }
- bool cross_ray_with_ray(point a, point b, point c, point d) {
- point pt;
- bool t = cross(line(a, b), line(c, d), pt);
- if (t == 0) return 0;
- return insight_ray(a, b, pt) && insight_ray(c, d, pt);
- }
- ld dist_ray_to_ray(point a, point b, point c, point d) {
- if (a == b && c == d) return (a - c).len();
- if (a == b) return dist_to_ray(c, d, a);
- if (c == d) return dist_to_ray(a, b, c);
- if (cross_ray_with_ray(a, b, c, d)) return 0;
- return min(min(dist_to_ray(a, b, c), dist_to_ray(a, b, d)), min(dist_to_ray(c, d, a), dist_to_ray(c, d, b)));
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- #ifdef arrias
- freopen("true.txt", "r", stdin);
- #endif
- cout.setf(ios::fixed);
- cout.precision(20);
- point a, b, c, d;
- cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
- /*set <pair<ld, ld>> st;
- st.insert({a.x, a.y});
- st.insert({b.x, b.y});
- st.insert({c.x, c.y});
- st.insert({d.x, d.y});
- assert(st.size() == 4);
- */
- cout << (a - c).len() << "\n";
- cout << dist_to_seg(c, d, a) << "\n";
- cout << dist_to_ray(c, d, a) << "\n";
- cout << dist(line(c, d), a) << "\n";
- cout << dist_to_seg(a, b, c) << "\n";
- cout << dist_seg_to_seg(a, b, c, d) << "\n";
- cout << dist_seg_to_ray(a, b, c, d) << "\n";
- cout << dist_seg_to_line(a, b, line(c, d)) << "\n";
- cout << dist_to_ray(a, b, c) << "\n";
- cout << dist_seg_to_ray(c, d, a, b) << "\n";
- cout << dist_ray_to_ray(a, b, c, d) << "\n";
- cout << dist_ray_to_line(a, b, line(c, d)) << "\n";
- cout << dist(line(a, b), c) << "\n";
- cout << dist_seg_to_line(c, d, line(a, b)) << "\n";
- cout << dist_ray_to_line(c, d, line(a, b)) << "\n";
- cout << dist(line(a, b), line(c, d)) << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement