typedef long double ld;

const ld EPS = 1e-9;

#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 sqrtl(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;
    }
};
//расстояние от точки до точки
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 {
        return sign((x - a) ^ (b - a)) == 0 &&
               sign((x - a) * (b - a)) == 1 &&
               sign((x - b) * (a - b)) == 1;
    }
}

struct Line {


};