Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- //#include "geometry.h"
- //#include "data_structure.h"
- using namespace std;
- using namespace chrono;
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define sqrtl(x) sqrt(x)
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef double ld;
- const ld EPS = 1e-6;
- #define Vec Point
- int sign(ld x) {
- if (x > EPS) return 1;
- if (x < -EPS) return -1;
- return 0;
- }
- ld sq(ld x) {
- return x * x;
- }
- struct Point {
- ld x, y;
- Point() : x(0), y(0) {}
- Point(ld _x, ld _y) : x(_x), y(_y) {}
- Point operator-(const Point& other) const {
- return Point(x - other.x, y - other.y);
- }
- Point operator+(const Point& other) const {
- return Point(x + other.x, y + other.y);
- }
- Point operator*(const ld& other) const {
- return Point(x * other, y * other);
- }
- // векторное произведение sin
- ld operator^(const Point& other) const {
- return x * other.y - y * other.x;
- }
- // скалярное произведение cos
- ld operator*(const Point& other) const {
- return x * other.x + y * other.y;
- }
- ld len2() const {
- return sq(x) + sq(y);
- }
- ld len() const {
- return sqrt(len2());
- }
- Point norm() const {
- ld d = len();
- return Point(x / d, y / d);
- }
- bool operator<(const Point& other) const {
- if (sign(x - other.x) != 0) {
- return x < other.x;
- }
- else if (sign(y - other.y) != 0) {
- return y < other.y;
- }
- return false;
- }
- bool operator==(const Point& other) const {
- return sign(x - other.x) == 0 && sign(y - other.y) == 0;
- }
- Point ort() {
- return Point(-y, x);
- }
- void deb() const {
- std::cerr << "(" << x << ", " << y << ")" << std::endl;
- }
- };
- struct Line {
- ld a, b, c;
- Line() : a(0), b(0), c(0) {}
- Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
- //// нормирование прямой
- ld d = Point(a, b).len();
- a /= d, b /= d, c /= d;
- if (sign(a) == -1) {
- a = -a;
- b = -b;
- c = -c;
- }
- else if (sign(a) == 0 && sign(b) == 0) {
- a = 0;
- b = -b;
- c = -b;
- }
- }/*
- Line norm() {
- ld d =
- }*/
- //ax+by+c=0
- ////y=-c/b
- //Line norm() {
- //
- //}
- Point get() {
- if (sign(b) != 0) {
- return Point(0, -c / b);
- }
- else
- return Point(0, -c);
- }
- bool operator==(const Line& other) const {
- return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c-other.c)==0;
- }
- };
- //расстояние от точки до точки
- ld dist_points(Point& a, Point& b) {
- return sqrtl(sq(a.x - b.x) + sq(a.y - b.y));
- }
- // угол между двумя векторами в радианах
- ld get_angle(const Vec& a, const Vec& b) {
- return atan2(a ^ b, a * b);
- }
- // проверка принадлежности точки отрезку
- bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
- // проверка в тупую
- return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
- //if (a == b) {
- // return a == x;
- //}
- //else if (a == x || b == x) {
- // return true;
- //}
- //else {
- // return sign((x - a) ^ (b - a)) == 0 &&
- // sign((x - a) * (b - a)) == 1 &&
- // sign((x - b) * (a - b)) == 1;
- //}
- }
- ld dist_line(const Point& a, const Line& l) {
- return abs(l.a * a.x + l.b * a.y + l.c) / sqrt(sq(l.a) + sq(l.b));
- }
- ld get_dist_line(Point& a, Point& c, Point& d) {
- Line buf(c, d);
- return dist_line(a, buf);
- }
- ld dist_point_segment(Point& x, Point& c, Point& d) {
- Line check(c, d);
- ld dis = dist_line(x, check);
- Vec k(check.a, check.b);
- k = k * dis;
- Point suba = x + k;
- Point subb = x - k;
- //dis = dist_points(suba, a);
- if (is_point_on_seg(c, d, suba) || is_point_on_seg(c, d, subb)) {
- return dis;
- }
- else {
- return min(dist_points(x, c), dist_points(x, d));
- }
- }
- ld get_dist_luch(Point& a, Point& c, Point& d) {
- Vec my = (d - c);
- Vec sec = (a - c);
- if (sign(sec * my) <= 0) {
- return dist_points(a, c);
- }
- else {
- return get_dist_line(a, c, d);
- }
- }
- bool cmp(Point& lht, Point& rht) {
- if (fabs(lht.x - rht.x) <= EPS) {
- return lht.y < rht.y;
- }
- return lht.x < rht.x;
- }
- bool line_cross(const Line& a, const Line& b, Point& ans) {
- ld d = (a.b * b.a - a.a * b.b);
- if (sign(d) == 0)
- return false;
- ans.x = (b.b * a.c - b.c * a.b) / d;
- ans.y = (b.c * a.a - a.c * b.a) / d;
- return true;
- }
- bool segment_cross(const Point& a, const Point& b, const Point& c, const Point& d) {
- if (sign((a - b) ^ (c - d)) == 0) {
- return is_point_on_seg(a, b, c) ||
- is_point_on_seg(a, b, d) ||
- is_point_on_seg(c, d, a) ||
- is_point_on_seg(c, d, b);
- }
- Point ans;
- if (line_cross(Line(a, b), Line(c, d), ans)) {
- return is_point_on_seg(a, b, ans) && is_point_on_seg(c, d, ans);
- }
- }
- ld dist_seg_to_seg(Point a, Point b, Point c, Point d) {
- if (segment_cross(a, b, c, d)) {
- return 0;
- }
- return min(min(dist_point_segment(a, c, d), dist_point_segment(b, c, d)), min(dist_point_segment(c, a, b), dist_point_segment(d, a, b)));
- /*if (!cmp(a, b)) {
- swap(a, b);
- }
- if (!cmp(c, d)) {
- swap(c, d);
- }
- if (segment_cross(a, b, c, d)) {
- return 0;
- }
- if (sign((d-a) * (b-a)) <= 0) {
- return dist_points(d, a);
- }
- if (sign((a - b) * (c-b)) <= 0) {
- return dist_points(b, c);
- }
- return min(min(dist_point_segment(a, c, d), dist_point_segment(b, c, d)), min(dist_point_segment(c, a, b), dist_point_segment(d, a, b)));*/
- }
- ld get_dist_seg_to_lunch(Point a, Point b, Point c, Point d) {
- Point ans;
- if (line_cross(Line(a, b), Line(c, d), ans)) {
- if (is_point_on_seg(a, b, ans) && sign((ans - c) * (d - c)) == 1) {
- return 0;
- }
- }
- // проверить на равенство прямых
- if (sign((b - c) * (d - c)) <= 0 && sign((a - c) * (d - c)) <= 0) {
- return min(dist_points(c, b), dist_points(c, a));
- }
- else {
- return min(dist_point_segment(c, a, b), min(get_dist_luch(a, c, d), get_dist_luch(b, c, d)));
- }
- }
- ld dist_seg_line(Point a, Point b, Point c, Point d) {
- Point ans;
- if (line_cross(Line(a, b), Line(c, d), ans)) {
- if (is_point_on_seg(a, b, ans))
- return 0;
- }
- return min(dist_line(a, Line(c, d)), dist_line(b, Line(c, d)));
- }
- bool check(Line lht, Line rht) {
- return lht==rht;
- }
- ld dist_luch_to_luch(Point& a, Point& b, Point& c, Point& d) {
- Point ans;
- if ((sign((b - a) ^ (d - c)) == 0)) {
- if (check(Line(a, b), Line(c, d))) {
- //a c b d
- if (is_point_on_seg(a, b, c)) {
- return 0;
- }
- }
- return min(get_dist_luch(a, c, d), get_dist_luch(c, a, b));
- }
- if (line_cross(Line(a, b), Line(c, d), ans)) {
- if (sign((ans - c) * (d - c)) == 1 && sign((ans - a) * (b - a)) == 1) {
- return 0;
- }
- }
- return min(dist_points(a, c), min(get_dist_luch(a, c, d), get_dist_luch(c, a, b)));
- }
- ld dist_luch_to_line(Point& a, Point& b, Point& c, Point& d) {
- if (sign((b - a) ^ (d - c)) == 0) {
- if (check(Line(a, b), Line(c, d))) {
- return 0;
- }
- return dist_line(a, Line(c, d));
- }
- Point ans;
- line_cross(Line(a, b), Line(c, d), ans);
- if (sign((ans - a) * (b - a)) == 1)
- return 0;
- else return dist_line(a, Line(c, d));
- }
- ld dist_line_to_line(Point& a, Point& b, Point& c, Point& d) {
- Line l1(a, b), l2(c, d);
- Point ans;
- if (l1 == l2)return 0.000000;
- if (line_cross(l1, l2,ans))return 0.000000;
- return fabs(l1.c - l2.c) / sqrtl(sq(l1.a) + sq(l1.b));
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- srand(time(NULL));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cout << fixed << setprecision(10);
- Point a, b, c, d;
- cin >> a.x >> a.y;
- cin >> b.x >> b.y;
- cin >> c.x >> c.y;
- cin >> d.x >> d.y;
- //cout << dist_seg_to_seg(a, b, c, d) << '\n';
- cout << dist_points(a, c) << '\n';
- // a [c,d];
- cout << dist_point_segment(a, c, d) << '\n';
- // a [(c,d),inf)
- cout << get_dist_luch(a, c, d) << '\n';
- //a (-inf,(c,d),inf)
- cout << get_dist_line(a, c, d) << '\n';
- // c [a,b]
- cout << dist_point_segment(c, a, b) << '\n';
- //[a,b] ; [c,d];
- cout << dist_seg_to_seg(a, b, c, d) << '\n';
- //cout << "расстояние от отрезка до лучаа" << endl;
- cout << get_dist_seg_to_lunch(a, b, c, d) << '\n';
- //расстояние от прямой до отрезка
- cout << dist_seg_line(a, b, c, d) << '\n';
- cout << get_dist_luch(c, a, b) << '\n';
- cout << get_dist_seg_to_lunch(c, d, a, b) << '\n';
- //расстояние от луча до луча
- cout << dist_luch_to_luch(a, b, c, d) << '\n';
- //расстояние от луча до прямой
- cout << dist_luch_to_line(a, b, c, d) << '\n';
- // расстояние от прямой до точки
- cout << get_dist_line(c, a, b) << '\n';
- cout << dist_seg_line(c, d, a, b) << '\n';
- //cout << ((b - a) ^ (d - c));
- cout << dist_luch_to_line(c, d, a, b) << '\n';
- cout << dist_line_to_line(a, b, c, d) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement