Hình học tính toán

struct Point {
    long long x, y;
    Point(long long x=0, long long y=0): x(x), y(y) {}
    Point operator-(const Point& p) const { return {x-p.x, y-p.y}; }
    Point operator+(const Point& p) const { return {x+p.x, y+p.y}; }
};

// Tích có hướng (cross product) của vector OA và OB
// > 0: B nằm bên trái OA (ngược chiều kim đồng hồ)
// < 0: B nằm bên phải OA (cùng chiều kim đồng hồ)
// = 0: A, O, B thẳng hàng
long long cross(Point O, Point A, Point B) {
    return (long long)(A.x-O.x)*(B.y-O.y) - (long long)(A.y-O.y)*(B.x-O.x);
}

// Tích vô hướng (dot product)
long long dot(Point A, Point B) { return A.x*B.x + A.y*B.y; }

// Khoảng cách bình phương (tránh sqrt)
long long dist2(Point A, Point B) {
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

bool point_in_triangle(Point P, Point A, Point B, Point C) {
    long long d1 = cross(A, B, P);
    long long d2 = cross(B, C, P);
    long long d3 = cross(C, A, P);
    bool has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
    return !(has_neg && has_pos);
}

// Kiểm tra hai đoạn AB và CD có giao nhau không
bool segments_intersect(Point A, Point B, Point C, Point D) {
    long long d1 = cross(C, D, A);
    long long d2 = cross(C, D, B);
    long long d3 = cross(A, B, C);
    long long d4 = cross(A, B, D);

    if (((d1>0&&d2<0)||(d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0)))
        return true;

    // Kiểm tra trường hợp thẳng hàng
    auto on_segment = [](Point P, Point A, Point B) {
        return min(A.x,B.x)<=P.x && P.x<=max(A.x,B.x)
            && min(A.y,B.y)<=P.y && P.y<=max(A.y,B.y);
    };
    if (d1==0 && on_segment(A,C,D)) return true;
    if (d2==0 && on_segment(B,C,D)) return true;
    if (d3==0 && on_segment(C,A,B)) return true;
    if (d4==0 && on_segment(D,A,B)) return true;
    return false;
}

long long polygon_area2(vector<Point>& pts) {
    long long area = 0;
    int n = pts.size();
    for (int i = 0; i < n; i++) {
        int j = (i+1) % n;
        area += pts[i].x * pts[j].y;
        area -= pts[j].x * pts[i].y;
    }
    return abs(area);   // diện tích thực = area/2
}