import math

class Point:
    """表示一个二维平面上的点"""
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    # 定义点的减法，用于生成向量
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __repr__(self):
        return f"({self.x}, {self.y})"

class Vector:
    """表示一个二维向量"""
    def __init__(self, x, y):
        self.x = x
        self.y = y

    @classmethod
    def from_points(cls, p1, p2):
        """从两个点创建向量"""
        return cls(p2.x - p1.x, p2.y - p1.y)

    # 向量加法
    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    # 向量减法
    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    # 标量乘法
    def __mul__(self, scalar):
        return Vector(self.x * scalar, self.y * scalar)

    # 计算向量的模（长度）
    def magnitude(self):
        return math.sqrt(self.x**2 + self.y**2)

    # 计算点积
    def dot(self, other):
        return self.x * other.x + self.y * other.y

    # 计算叉积
    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def __repr__(self):
        return f"<{self.x}, {self.y}>"

def cross_product_sign(p, q, r):
    """计算向量 pq 和 pr 的叉积符号，用于判断方向。
       返回值: 1(逆时针), -1(顺时针), 0(共线)"""
    vec_pq = Vector.from_points(p, q)
    vec_pr = Vector.from_points(p, r)
    cp = vec_pq.cross(vec_pr)
    if cp > 0:
        return 1  # 逆时针
    elif cp < 0:
        return -1 # 顺时针
    else:
        return 0  # 共线

def segments_intersect(p1, p2, p3, p4):
    """判断线段(p1,p2)和线段(p3,p4)是否相交。
       使用叉积法：需要满足两个条件。"""
    # 条件1: 线段p1p2的端点p3, p4应在其两侧。
    d1 = cross_product_sign(p1, p2, p3)
    d2 = cross_product_sign(p1, p2, p4)

    # 条件2: 线段p3p4的端点p1, p2应在其两侧。
    d3 = cross_product_sign(p3, p4, p1)
    d4 = cross_product_sign(p3, p4, p2)

    # 一般情况：每个线段的两个端点分别在另一线段的两侧。
    if (d1 * d2 < 0) and (d3 * d4 < 0):
        return True

    # 特殊情况：处理三点共线且重叠的情况（简化版，实际竞赛需更严谨）
    # 这里仅演示思路，不包含所有边界情况。
    # 可检查点是否在对方线段上（使用点积判断投影是否在线段内）
    # 完整的算法需要考虑更多边界情况。
    return False

# --- 测试代码 ---
if __name__ == "__main__":
    # 创建点
    A = Point(0, 0)
    B = Point(4, 0)
    C = Point(2, 3)
    D = Point(2, -1)

    # 测试叉积符号 (方向判断)
    print(f"点 C(2,3) 相对于线段 AB(0,0)->(4,0) 的位置: ", end="")
    direction = cross_product_sign(A, B, C)
    if direction == 1:
        print("左侧 (逆时针)")
    elif direction == -1:
        print("右侧 (顺时针)")
    else:
        print("在线上 (共线)")

    print(f"点 D(2,-1) 相对于线段 AB(0,0)->(4,0) 的位置: ", end="")
    direction = cross_product_sign(A, B, D)
    if direction == 1:
        print("左侧 (逆时针)")
    elif direction == -1:
        print("右侧 (顺时针)")
    else:
        print("在线上 (共线)")

    # 测试线段相交
    P1, P2 = Point(0, 0), Point(2, 2)
    P3, P4 = Point(0, 2), Point(2, 0)
    print(f"\n线段 P1P2(0,0)-(2,2) 和 线段 P3P4(0,2)-(2,0) 是否相交? {segments_intersect(P1, P2, P3, P4)}")

    P1, P2 = Point(0, 0), Point(1, 1)
    P3, P4 = Point(1, 0), Point(2, 1)
    print(f"线段 P1P2(0,0)-(1,1) 和 线段 P3P4(1,0)-(2,1) 是否相交? {segments_intersect(P1, P2, P3, P4)}")

点积: 5
叉积: -5
v 相对于 u 的方向: 顺时针 (右侧)

print(turn_direction(Point(0,0), Point(1,1), Point(2,0))) # 应输出 “右转”
print(turn_direction(Point(0,0), Point(1,1), Point(0,2))) # 应输出 “左转”
print(turn_direction(Point(0,0), Point(2,2), Point(1,1))) # 应输出 “共线”