Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- using namespace std;
- double sqr(double a) // квадрат числа
- {
- return a * a;
- }
- bool doubleEqual(double a, double b) // сравниваем на равенство с eps, константой 1е-9 используется только здесь
- {
- return fabs(a - b) < 1e-9;
- }
- bool doubleLessOrEqual(double a, double b) // <= с eps
- {
- return a < b || doubleEqual(a, b);
- }
- bool doubleLess(double a, double b) // < с eps
- {
- return a < b && !doubleEqual(a, b);
- }
- bool doubleGreaterOrEqual(double a, double b) // >= с eps
- {
- return a > b || doubleEqual(a, b);
- }
- bool doubleGreater(double a, double b) // > с eps
- {
- return a > b && !doubleEqual(a, b);
- }
- double mySqrt(double a) // mySqrt с проверкой, что корректен аргумент
- {
- if(doubleLess(a, 0) ) //некорректный вызов
- {
- throw "sqrt(-1)";
- }
- if(a < 0) return 0; //отрицательное ввиду небольшой погрешности
- return sqrt(a);
- }
- struct Point{ // класс точки или вектора, далее мы эти понятия разделять не будем
- // но условимся (для удобного чтения) большими буквами обозначать точки (A, B, C, D, ...)
- // маленькими - вектора(v, u, w,...)
- double x, y; // 2 приватных поля, других не будет
- Point(): x(0), y(0) {} // конструктор по умолчанию
- Point(double x, double y): x(x), y(y) {} // намеренно сделаем два конструктора вместо Point(x = 0...)
- //Это избавит нас от ошибок вида Point A = 2;
- void scan() // читаем координаты точки
- {
- scanf("%lf %lf", &x, &y);
- }
- void print() const // выводим координаты точки
- {
- printf("%.10lf %.10lf\n", x, y);
- }
- Point operator+(const Point & p) const // сложение 2х векторов
- {
- return Point(x + p.x, y + p.y);
- }
- Point operator-(const Point & p) const // вычитание 2х векторов
- {
- return Point(x - p.x, y - p.y);
- }
- Point operator-() const // обратный вектор
- {
- return Point(-x, -y);
- }
- Point operator*(double k) const // умножение вектора на скаляр
- {
- return Point(x * k, y * k);
- }
- Point operator/(double k) const // деление вектора на скаляр
- {
- return Point(x / k, y / k);
- }
- double operator%(const Point & p) const // скалярное произведение
- {
- return x * p.x + y * p.y;
- }
- double operator*(const Point & p) const // векторное произведение
- {
- return x * p.y - y * p.x;
- }
- double length() const // длина вектора по определению из ан.гема (корень из скалярного квадрата)
- {
- return mySqrt(*this % *this);
- }
- double distTo(const Point & p) const //расстояние между 2мя точками - модуль вектора между ними
- {
- return (*this - p).length();
- }
- double distTo(const Point & A, const Point & B) const // расстояние от точки до прямой (всегда >= 0)
- {
- double d = A.distTo(B);
- if(doubleEqual(d, 0) ) // прямая должна задаваться двумя! точками
- {
- throw "A = B";
- }
- double s = (*this - A) * (*this - B); // удвоенная площадь треугольника
- return fabs(s) / d; // метод площадей
- }
- Point normalize(double k = 1) const // выставляет длину вектора в k
- {
- double len = length(); // Текущая длина
- if(doubleEqual(len, 0) ) // если длина ноль
- {
- if(doubleEqual(k, 0) )
- {
- return Point();
- }
- throw "zero-size vector"; //кроме нулевой никакую получить не можем
- }
- return *this * (k / len);
- }
- Point getH(const Point & A, const Point & B) const // опускаем высоту из точки на прямую (A, B)
- {
- Point C = *this;
- Point v = B - A; // направляющий вектор прямой
- Point u = C - A; // вектор, проекция которого нам нужна
- double k = v % u / v.length(); // нашли длину проекции
- v = v.normalize(k); // нашли проекцию u на v
- Point H = A + v; // подвинули точку A в проекцию конца вектора u, отложенного из A
- return H;
- }
- Point rotate() const // поворот на 90 градусов против часовой стрелки (положительное направление)
- {
- return Point(-y, x);
- }
- Point rotate(double alpha) const // поворот на угол alpha против часовой стрелки
- // (по часовой стрелке, если alpha < 0)
- {
- return rotate(cos(alpha), sin(alpha) ); // делегируем задачу другому экземпляру функции
- }
- Point rotate(double cosa, double sina) const // поворот с заданными косинусом и синусом
- {
- Point v = *this;
- Point u = v.rotate(); // вектор, перпендикулярный v, теперь (v, u) - базис, в котором мы знаем ответ
- Point w = v * cosa + u * sina; // зная координаты в базисе (v, u), нашли w
- return w;
- }
- bool isZero() const // проверка на то, что точка нулевая без сложных операций и погрешности
- {
- return doubleEqual(x, 0) && doubleEqual(y, 0);
- }
- bool isOnLine(const Point & A, const Point & B) const // точка на прямой?
- {
- return doubleEqual( (A - *this) * (B - *this), 0);
- }
- bool isInSegment(const Point & A, const Point & B) const // точка внутри отрезка?
- {
- return isOnLine(A, B) && doubleLessOrEqual( (A - *this) % (B - *this), 0 );
- }
- bool isInSegmentStrictly(const Point & A, const Point & B) const // точка внутри отрезка строго?
- {
- return isOnLine(A, B) && doubleLess( (A - *this) % (B - *this), 0 );
- }
- double getAngle() const
- {
- return atan2(y, x); // угол между вектором и осью ОХ
- }
- double getAngle(Point u) const
- {
- Point v = *this;
- return atan2(v * u, v % u); // ориентированный угол между векторами
- }
- };
- int getIntersection // ищем пересечение прямой (A, B) и прямой (C, D)
- (
- const Point & A,
- const Point & B,
- const Point & C,
- const Point & D,
- Point & O
- )
- {
- Point v = B - A; // направляющий вектор прямой (A, B)
- double s1 = (C - A) * (D - A); // площадь треугольника A, C, D
- double s2 = (D - B) * (C - B); // площадь треугольника B, D, C
- double s = s1 + s2; // площадь четурёхугольника
- if(doubleEqual(s, 0) ) // прямые параллельны (или совпадают)
- {
- if(!A.isOnLine(C, D) ) // прямые параллельны
- {
- return 0; // пересечение пусто
- }
- return 2; // больше 1ой точки в пересечении
- }
- v = v / s;
- v = v * s1; // вектора AO и AB пропорциональны площадям s1 и s
- O = A + v; // нашли точку пересечения
- return 1; // 1 точка в пересечении
- }
- int main(){
- Point o, a, b;
- o.scan();
- a.scan();
- b.scan();
- if(o.isInSegment(a, b)){
- cout << "YES";
- }
- else{
- cout << "NO";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement