Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- typedef long long ll;
- const ld EPS = 1e-9;
- struct Point
- {
- ld x, y;
- Point operator + (const Point& B)
- {
- return {B.x + x, B.y + y};
- }
- Point operator - (const Point& B)
- {
- return {B.x - x, B.y - y};
- }
- ld operator ^ (const Point& B)
- {
- return x * B.y - y * B.x;
- }
- ld operator * (const Point& B)
- {
- return x * B.x + y * B.y;
- }
- };
- struct Line
- {
- ld a, b, c;
- };
- Point makePoint(ll x, ll y)
- {
- Point p;
- p.x = x;
- p.y = y;
- return p;
- }
- Line makeLine(ld a, ld b, ld c)
- {
- Line l;
- l.a = a;
- l.b = b;
- l.c = c;
- return l;
- }
- Line makeLine(Point p1, Point p2)
- {
- Line l;
- l.a = p1.y - p2.y;
- l.b = p2.x - p1.x;
- l.c = p1.x * p2.y - p2.x * p1.y;
- return l;
- }
- Point readPoint()
- {
- Point p;
- cin >> p.x >> p.y;
- return p;
- }
- ld length(Point p)
- {
- return sqrt(p.x * p.x + p.y * p.y);
- }
- ld Distance(Point p, Point A, Point B)
- {
- Line l = makeLine(A, B);
- return (abs)(l.a * p.x + l.b * p.y + l.c) / sqrt(l.a * l.a + l.b * l.b);
- }
- bool checkParallel(Line l1, Line l2)
- {
- return abs(l1.a * l2.b - l2.a * l1.b) < EPS;
- }
- Point LineIntersec(Line l1, Line l2)
- {
- Point p;
- p.x = -(l1.c * l2.b - l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b);
- p.y = -(l1.a * l2.c - l2.a * l1.c) / (l1.a * l2.b - l2.a * l1.b);
- return p;
- }
- bool PointonSegment(Point p1, Point p2, Point p)
- {
- Line l = makeLine(p1, p2);
- if (abs(l.a * p.x + l.b * p.y + l.c) > EPS)
- return false;
- return p.x - max(p1.x, p2.x) < EPS && p.x - min(p1.x, p2.x) > -EPS &&
- p.y - max(p1.y, p2.y) < EPS && p.y - min(p1.y, p2.y) > -EPS;
- }
- bool PointonRay(Point C, Point D, Point A)
- {
- if (abs(A.x - C.x) + abs(A.y - C.y) < EPS)
- return true;
- Line l = makeLine(C, D);
- if (abs(l.a * A.x + l.b * A.y + l.c) > EPS)
- return false;
- if (abs(C.x + C.y - D.x - D.y) < EPS)
- return ((C.x - D.x) * (C.x - A.x) > 0);
- if (D.x + D.y > C.x + C.y)
- return (A.x + A.y >= C.x + C.y);
- return (A.x + A.y <= C.x + C.y);
- }
- bool RaySegmentIntersec(Point C, Point D, Point A, Point B)
- {
- Line l1 = makeLine(A, B);
- Line l2 = makeLine(C, D);
- if (checkParallel(l1, l2))
- {
- if (abs(l1.a * l2.c - l2.a * l1.c) > EPS)
- return false;
- return (PointonRay(C, D, A) || PointonRay(C, D, B));
- }
- Point p = LineIntersec(l1, l2);
- return (PointonSegment(A, B, p) && PointonRay(C, D, p));
- }
- bool SegmentIntersec(Point A, Point B, Point C, Point D)
- {
- return RaySegmentIntersec(A, B, C, D) && RaySegmentIntersec(B, A, C, D);
- }
- bool RaysIntersec(Point A, Point B, Point C, Point D)
- {
- Line l1 = makeLine(A, B);
- Line l2 = makeLine(C, D);
- if (checkParallel(l1, l2))
- {
- if (abs(l1.a * l2.c - l2.a * l1.c) > EPS)
- return false;
- return (PointonRay(A, B, C) || PointonRay(C, D, A));
- }
- Point p = LineIntersec(l1, l2);
- return (PointonRay(A, B, p) && PointonRay(C, D, p));
- }
- bool RayLineIntersec(Point A, Point B, Point C, Point D)
- {
- return RaysIntersec(A, B, C, D) || RaysIntersec(A, B, D, C);
- }
- ld DistanceRayPoint(Point A, Point B, Point C)
- {
- if (((B - A) ^ (C - A)) < 0)
- return length(A - C);
- return Distance(C, A, B);
- }
- ld DistanceSegmentPoint(Point A, Point B, Point C)
- {
- return max(DistanceRayPoint(A, B, C), DistanceRayPoint(B, A, C));
- }
- ld DistanceSegments(Point A, Point B, Point C, Point D)
- {
- if (SegmentIntersec(A, B, C, D))
- return 0;
- return min(min(DistanceSegmentPoint(A, B, C), DistanceSegmentPoint(A, B, D)),
- min(DistanceSegmentPoint(C, D, A), DistanceSegmentPoint(C, D, B)));
- }
- ld DistanceRays(Point A, Point B, Point C, Point D)
- {
- if (RaysIntersec(A, B, C, D))
- return 0;
- return min(DistanceRayPoint(C, D, A), DistanceRayPoint(A, B, C));
- }
- ld DistanceRaySegment(Point C, Point D, Point A, Point B)
- {
- return max(DistanceRays(C, D, A, B), DistanceRays(C, D, B, A));
- }
- ld DistanceRayLine(Point A, Point B, Point C, Point D)
- {
- if (RayLineIntersec(A, B, C, D))
- return 0;
- return Distance(A, C, D);
- }
- ld DistanceLineSegment(Point C, Point D, Point A, Point B)
- {
- if (RaySegmentIntersec(C, D, A, B) || RaySegmentIntersec(D, C, A, B))
- return 0;
- return min(Distance(A, C, D), Distance(B, C, D));
- }
- int main()
- {
- freopen("hard-geometry.in", "r", stdin);
- freopen("hard-geometry.out", "w", stdout);
- cout.precision(20);
- Point A = readPoint(), B = readPoint(), C = readPoint(), D = readPoint();
- cout << length(C - A) << endl;
- cout << DistanceSegmentPoint(C, D, A) << endl;
- cout << DistanceRayPoint(C, D, A) << endl;
- cout << Distance(A, C, D) << endl;
- cout << DistanceSegmentPoint(A, B, C) << endl;
- cout << DistanceSegments(A, B, C, D) << endl;
- cout << DistanceRaySegment(C, D, A, B) << endl;
- cout << DistanceLineSegment(C, D, A, B) << endl;
- cout << DistanceRayPoint(A, B, C) << endl;
- cout << DistanceRaySegment(A, B, C, D) << endl;
- cout << DistanceRays(A, B, C, D) << endl;
- cout << DistanceRayLine(A, B, C, D) << endl;
- cout << Distance(C, A, B) << endl;
- cout << DistanceLineSegment(A, B, C, D) << endl;
- cout << DistanceRayLine(C, D, A, B) << endl;
- Line AB = makeLine(A, B);
- Line CD = makeLine(C, D);
- if (checkParallel(AB, CD))
- cout << Distance(A, C, D) << endl;
- else
- cout << 0 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement