Геометрические примитивы: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
== Точки, прямые, лучи, отрезки, многоугольники ==
== Точки, прямые, лучи, отрезки, многоугольники ==


  #include <stdio.h>
  #include <algorithm>
  #include <math.h>
  #include <cmath>
  #include <vector>
  #include <vector>
#include <algorithm>
  using namespace std;
  using namespace std;
   
   
  const double EPS = 1e-9;
  const double EPS = 1e-9;
   
   
  struct Point {
  struct Point {
Строка 14: Строка 12:
   
   
     Point() {}
     Point() {}
     Point(double x, double y) : x(x), y(y) {}
     Point(double x, double y) : x(x), y(y) {}
     Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}
     Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}
    bool operator == (const Point &that) const {
        return fabs(x - that.x) < EPS && fabs(y - that.y) < EPS;
    }
    bool operator != (const Point &that) const {
        return !(*this == that);
    }
   
   
     double angle() const {
     double angle() const {
Строка 23: Строка 31:
         return a;
         return a;
     }
     }
     double length() const {
     double length() const {
         return sqrt(x * x + y * y);
         return hypot(x, y);
     }
     }
     double distanceTo(const Point &that) const {
     double distanceTo(const Point &that) const {
         return Point(*this, that).length();
         return Point(*this, that).length();
Строка 33: Строка 43:
         return Point(x + that.x, y + that.y);
         return Point(x + that.x, y + that.y);
     }
     }
     Point operator - (const Point &that) const {
     Point operator - (const Point &that) const {
         return Point(x - that.x, y - that.y);
         return Point(x - that.x, y - that.y);
     }
     }
     Point operator * (double k) const {
     Point operator * (double k) const {
         return Point(x * k, y * k);
         return Point(x * k, y * k);
     }  
     }
     Point setLength(double newLength) const {
     Point setLength(double newLength) const {
         double k = newLength / length();
         double k = newLength / length();
Строка 46: Строка 59:
     double dotProduct(const Point &that) const {
     double dotProduct(const Point &that) const {
         return x * that.x + y * that.y;
         return x * that.x + y * that.y;
     }  
     }
     double angleTo(const Point &that) const {
     double angleTo(const Point &that) const {
         return acos(max(-1.0, min(1.0, dotProduct(that) / (length() * that.length()))));
         return acos(max(-1.0, min(1.0, dotProduct(that) / (length() * that.length()))));
     }  
     }
     bool isOrthogonalTo(const Point &that) const {
     bool isOrthogonalTo(const Point &that) const {
         return fabs(dotProduct(that)) < EPS;
         return fabs(dotProduct(that)) < EPS;
     }  
     }
     Point orthogonalPoint() const {
     Point orthogonalPoint() const {
         return Point(-y, x);
         return Point(-y, x);
Строка 60: Строка 76:
         return x * that.y - y * that.x;
         return x * that.y - y * that.x;
     }
     }
     bool isCollinearTo(const Point &that) const {
     bool isCollinearTo(const Point &that) const {
         return fabs(crossProduct(that)) < EPS;
         return fabs(crossProduct(that)) < EPS;
     }
     }
  };
  };
   
   
  struct Line {
  struct Line {
Строка 70: Строка 86:
   
   
     Line() {}
     Line() {}
     Line(double a, double b, double c) : a(a), b(b), c(c) {}
     Line(double a, double b, double c) : a(a), b(b), c(c) {}
     Line(const Point &p1, const Point &p2) : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
     Line(const Point &p1, const Point &p2) : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
     static Line LineByVector(const Point &p, const Point &v) {
     static Line LineByVector(const Point &p, const Point &v) {
         return Line(p, p + v);
         return Line(p, p + v);
     }
     }
     static Line LineByNormal(const Point &p, const Point &n) {
     static Line LineByNormal(const Point &p, const Point &n) {
         return LineByVector(p, n.orthogonalPoint());
         return LineByVector(p, n.orthogonalPoint());
Строка 82: Строка 102:
         return Point(a, b);
         return Point(a, b);
     }
     }
     Line orthogonalLine(const Point &p) const {
     Line orthogonalLine(const Point &p) const {
         return LineByVector(p, normal());
         return LineByVector(p, normal());
     }  
     }
     Line parallelLine(const Point &p) const {
     Line parallelLine(const Point &p) const {
         return LineByNormal(p, normal());
         return LineByNormal(p, normal());
     }
     }
     Line parallelLine(double distance) const {
     Line parallelLine(double distance) const {
         Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
         Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
Строка 101: Строка 124:
             return r > 0 ? 1 : -1;
             return r > 0 ? 1 : -1;
     }
     }
     double distanceTo(const Point &p) const {
     double distanceTo(const Point &p) const {
         return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
         return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
     }
     }
     bool has(const Point &p) const {
     bool has(const Point &p) const {
         return distanceTo(p) < EPS;
         return distanceTo(p) < EPS;
Строка 114: Строка 139:
         } else
         } else
             return 0;
             return 0;
     }  
     }
     bool intersectsWith(const Line &that) const {
     bool intersectsWith(const Line &that) const {
         return distanceTo(that) < EPS;
         return distanceTo(that) < EPS;
     }
     }
     Point intersection(const Line &that) const {
     Point intersection(const Line &that) const {
         double d = a * that.b - b * that.a;
         double d = a * that.b - b * that.a;
Строка 123: Строка 150:
         double dy = a * -that.c - -c * that.a;
         double dy = a * -that.c - -c * that.a;
         return Point(dx / d, dy / d);
         return Point(dx / d, dy / d);
     }  
     }
  };
  };
   
   
  struct Ray {
  struct Ray {
Строка 132: Строка 158:
   
   
     Ray(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
     Ray(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
   
     double distanceTo(const Point &p) const {
     double distanceTo(const Point &p) const {
         if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS)
         if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS)
Строка 139: Строка 165:
             return p1.distanceTo(p);
             return p1.distanceTo(p);
     }
     }
     bool has(const Point &p) const {
     bool has(const Point &p) const {
         return distanceTo(p) < EPS;
         return distanceTo(p) < EPS;
Строка 152: Строка 179:
         return min(distanceTo(that.p1), that.distanceTo(p1));
         return min(distanceTo(that.p1), that.distanceTo(p1));
     }
     }
     bool intersectsWith(const Ray &that) const {
     bool intersectsWith(const Ray &that) const {
         return distanceTo(that) < EPS;
         return distanceTo(that) < EPS;
     }
     }
  };
  };
   
   
  struct Segment {
  struct Segment {
Строка 163: Строка 190:
   
   
     Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
     Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
   
     double distanceTo(const Point &p) const {
     double distanceTo(const Point &p) const {
         if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS && Point(p2, p).dotProduct(Point(p2, p1)) >= -EPS)
         if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS && Point(p2, p).dotProduct(Point(p2, p1)) >= -EPS)
Строка 170: Строка 197:
             return min(p1.distanceTo(p), p2.distanceTo(p));
             return min(p1.distanceTo(p), p2.distanceTo(p));
     }
     }
     bool has(const Point &p) const {
     bool has(const Point &p) const {
         return distanceTo(p) < EPS;
         return distanceTo(p) < EPS;
Строка 182: Строка 210:
         }
         }
         return min(min(distanceTo(that.p1), distanceTo(that.p2)), min(that.distanceTo(p1), that.distanceTo(p2)));
         return min(min(distanceTo(that.p1), distanceTo(that.p2)), min(that.distanceTo(p1), that.distanceTo(p2)));
     }  
     }
     bool intersectsWith(const Segment &that) const {
     bool intersectsWith(const Segment &that) const {
         return distanceTo(that) < EPS;
         return distanceTo(that) < EPS;
     }
     }
  };
  };
   
   
  struct Polygon {
  struct Polygon {
     vector<Point> points;
     vector<Point> points;
     void addPoint(const Point &p) {
     void addPoint(const Point &p) {
         points.push_back(p);
         points.push_back(p);
     }
     }
    bool has(const Point &p) const {
        bool pos = 0, neg = 0;
        for (int i = 0; i < points.size(); i++) {
            const Point &a = points[i], &b = points[(i + 1) % points.size()];
            Point ab(a, b), ap(a, p);
            double cross = ab.crossProduct(ap);
            pos |= cross > EPS;
            neg |= cross < -EPS;
        }
        return !pos || !neg;
    }
    double perimeter() const {
        double p = 0;
        for (int i = 0; i < points.size(); i++)
            p += points[i].distanceTo(points[(i + 1) % points.size()]);
        return p;
    }
     double area() const {
     double area() const {
         double s = 0;
         double s = 0;
         for (int i = 1; i < points.size(); i++)
         for (int i = 0; i < points.size(); i++)
             s += points[i - 1].crossProduct(points[i]);
             s += points[i].crossProduct(points[(i + 1) % points.size()]);
        s += points[points.size() - 1].crossProduct(points[0]);
         return fabs(s) / 2;
         return fabs(s) / 2;
     }
     }

Версия от 01:26, 13 августа 2021

Точки, прямые, лучи, отрезки, многоугольники

#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double EPS = 1e-9;

struct Point {
    double x, y;

    Point() {}

    Point(double x, double y) : x(x), y(y) {}

    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

    bool operator == (const Point &that) const {
        return fabs(x - that.x) < EPS && fabs(y - that.y) < EPS;
    }

    bool operator != (const Point &that) const {
        return !(*this == that);
    }

    double angle() const {
        double a = atan2(y, x);
        if (a < -EPS)
            a += 2 * acos(-1.0);
        return a;
    }

    double length() const {
        return hypot(x, y);
    }

    double distanceTo(const Point &that) const {
        return Point(*this, that).length();
    }

    Point operator + (const Point &that) const {
        return Point(x + that.x, y + that.y);
    }

    Point operator - (const Point &that) const {
        return Point(x - that.x, y - that.y);
    }

    Point operator * (double k) const {
        return Point(x * k, y * k);
    }

    Point setLength(double newLength) const {
        double k = newLength / length();
        return Point(x * k, y * k);
    }

    double dotProduct(const Point &that) const {
        return x * that.x + y * that.y;
    }

    double angleTo(const Point &that) const {
        return acos(max(-1.0, min(1.0, dotProduct(that) / (length() * that.length()))));
    }

    bool isOrthogonalTo(const Point &that) const {
        return fabs(dotProduct(that)) < EPS;
    }

    Point orthogonalPoint() const {
        return Point(-y, x);
    }

    double crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }

    bool isCollinearTo(const Point &that) const {
        return fabs(crossProduct(that)) < EPS;
    }
};

struct Line {
    double a, b, c;

    Line() {}

    Line(double a, double b, double c) : a(a), b(b), c(c) {}

    Line(const Point &p1, const Point &p2) : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    static Line LineByVector(const Point &p, const Point &v) {
        return Line(p, p + v);
    }

    static Line LineByNormal(const Point &p, const Point &n) {
        return LineByVector(p, n.orthogonalPoint());
    }

    Point normal() const {
        return Point(a, b);
    }

    Line orthogonalLine(const Point &p) const {
        return LineByVector(p, normal());
    }

    Line parallelLine(const Point &p) const {
        return LineByNormal(p, normal());
    }

    Line parallelLine(double distance) const {
        Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
        Point p1 = p + normal().setLength(distance);
        return LineByNormal(p1, normal());
    }

    int side(const Point &p) const {
        double r = a * p.x + b * p.y + c;
        if (fabs(r) < EPS)
            return 0;
        else
            return r > 0 ? 1 : -1;
    }

    double distanceTo(const Point &p) const {
        return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Line &that) const {
        if (normal().isCollinearTo(that.normal())) {
            Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
            return that.distanceTo(p);
        } else
            return 0;
    }

    bool intersectsWith(const Line &that) const {
        return distanceTo(that) < EPS;
    }

    Point intersection(const Line &that) const {
        double d = a * that.b - b * that.a;
        double dx = -c * that.b - b * -that.c;
        double dy = a * -that.c - -c * that.a;
        return Point(dx / d, dy / d);
    }
};

struct Ray {
    Point p1, p2;
    double a, b, c;

    Ray(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    double distanceTo(const Point &p) const {
        if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS)
            return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
        else
            return p1.distanceTo(p);
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Ray &that) const {
        Line l(a, b, c), thatL(that.a, that.b, that.c);
        if (l.intersectsWith(thatL)) {
            Point p = l.intersection(thatL);
            if (has(p) && that.has(p))
                return 0;
        }
        return min(distanceTo(that.p1), that.distanceTo(p1));
    }

    bool intersectsWith(const Ray &that) const {
        return distanceTo(that) < EPS;
    }
};

struct Segment {
    Point p1, p2;
    double a, b, c;

    Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    double distanceTo(const Point &p) const {
        if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS && Point(p2, p).dotProduct(Point(p2, p1)) >= -EPS)
            return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
        else
            return min(p1.distanceTo(p), p2.distanceTo(p));
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Segment &that) const {
        Line l(a, b, c), thatL(that.a, that.b, that.c);
        if (l.intersectsWith(thatL)) {
            Point p = l.intersection(thatL);
            if (has(p) && that.has(p))
                return 0;
        }
        return min(min(distanceTo(that.p1), distanceTo(that.p2)), min(that.distanceTo(p1), that.distanceTo(p2)));
    }

    bool intersectsWith(const Segment &that) const {
        return distanceTo(that) < EPS;
    }
};

struct Polygon {
    vector<Point> points;

    void addPoint(const Point &p) {
        points.push_back(p);
    }

    bool has(const Point &p) const {
        bool pos = 0, neg = 0;
        for (int i = 0; i < points.size(); i++) {
            const Point &a = points[i], &b = points[(i + 1) % points.size()];
            Point ab(a, b), ap(a, p);
            double cross = ab.crossProduct(ap);
            pos |= cross > EPS;
            neg |= cross < -EPS;
        }
        return !pos || !neg;
    }

    double perimeter() const {
        double p = 0;
        for (int i = 0; i < points.size(); i++)
            p += points[i].distanceTo(points[(i + 1) % points.size()]);
        return p;
    }

    double area() const {
        double s = 0;
        for (int i = 0; i < points.size(); i++)
            s += points[i].crossProduct(points[(i + 1) % points.size()]);
        return fabs(s) / 2;
    }
};

Точная проверка на пересечение отрезков с целыми координатами

struct Point {
    long long x, y;

    Point() {}
    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

    long long crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }
};


struct Segment {
    Point p1, p2;

    Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2) {}

    bool intersectsWith(const Segment &that) const {
        long long abx1 = min(p1.x, p2.x), abx2 = max(p1.x, p2.x);
        long long cdx1 = min(that.p1.x, that.p2.x), cdx2 = max(that.p1.x, that.p2.x);
        if (max(abx1, cdx1) > min(abx2, cdx2))
            return 0;

        long long aby1 = min(p1.y, p2.y), aby2 = max(p1.y, p2.y);
        long long cdy1 = min(that.p1.y, that.p2.y), cdy2 = max(that.p1.y, that.p2.y);
        if (max(aby1, cdy1) > min(aby2, cdy2))
            return 0;

        Point ab(p1, p2), ac(p1, that.p1), ad(p1, that.p2);
        long long abc = ab.crossProduct(ac), abd = ab.crossProduct(ad);
        if (abc > 0 && abd > 0 || abc < 0 && abd < 0)
            return 0;

        Point cd(that.p1, that.p2), ca(that.p1, p1), cb(that.p1, p2);
        long long cda = cd.crossProduct(ca), cdb = cd.crossProduct(cb);
        if (cda > 0 && cdb > 0 || cda < 0 && cdb < 0)
            return 0;

        return 1;
    }
};

Ссылки

Теория:

Задачи: