import random


def cross_product(p1, p2, p3):
    """
    计算向量 p1p2 和 p1p3 的叉积。
    如果结果为正，则 p1p3 在 p1p2 的顺时针方向；
    如果结果为负，则 p1p3 在 p1p2 的逆时针方向；
    如果结果为零，则 p1、p2 和 p3 共线。
    """
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])


def do_segments_intersect(s1, s2):
    """
    判断两条线段 s1 和 s2 是否相交。
    每条线段由两个点的元组表示，例如：s1 = ((x1, y1), (x2, y2))。
    """
    p1, p2 = s1
    p3, p4 = s2
    if max(p1[0], p2[0]) <= min(p3[0], p4[0]):
        return False  # 线段1在线段2的左侧
    if max(p3[0], p4[0]) <= min(p1[0], p2[0]):
        return False  # 线段1在线段2的右侧
    if max(p1[1], p2[1]) <= min(p3[1], p4[1]):
        return False  # 线段1在线段2的下方
    if max(p3[1], p4[1]) <= min(p1[1], p2[1]):
        return False  # 线段1在线段2的上方
    if cross_product(p1, p2, p3) * cross_product(p1, p2, p4) >= 0:
        return False  # 线段2的两个端点在线段1的同侧
    if cross_product(p3, p4, p1) * cross_product(p3, p4, p2) >= 0:
        return False  # 线段1的两个端点在线段2的同侧
    return True  # 两条线段相交


def is_over_k_line(combination, triangle_index):
    bottom_length = combination[triangle_index]
    if bottom_length == 0:
        return False

    left_b_x = K_COUNT - sum(combination[triangle_index:])
    left_b_y = lowest
    left_t_x = middle = left_b_x + int(bottom_length / 2)
    left_t_y = low[left_t_x]

    right_b_x = left_b_x + bottom_length - 1
    right_b_y = lowest
    right_t_x = middle
    right_t_y = left_t_y

    line_left = [[left_b_x, left_b_y], [left_t_x, left_t_y]]
    line_right = [[right_b_x, right_b_y], [right_t_x, right_t_y]]

    k_index = left_b_x
    while k_index <= right_b_x:
        k = [[k_index, low[k_index]], [k_index, high[k_index]]]

        # 在垂线左侧的K只用考虑三角形的左边；右侧只考虑右边，并且垂线不做判断
        if k_index < middle and do_segments_intersect(line_left, k):
            return True
        if k_index > middle and do_segments_intersect(line_right, k):
            return True

        k_index = k_index + 1

    return False


def generate_combinations(n, k_count, step, min_length, init_value):
    # Initialize the combination
    combination = []

    space_step = 4
    space_max = 12

    c_index = 0
    # 初始间隔
    combination.append(0)
    while c_index < n:
        # 三角形
        combination.append(init_value)
        # 间隔
        combination.append(0)
        c_index = c_index + 1

    # Generate all combinations
    count = 0
    while True:
        # Print the current combination
        # print(combination)
        count += 1

        # Increment the combination
        i = len(combination) - 1
        while i >= 0:
            # 如果下标是偶数，则该位置是空位，是三角形之间的距离
            # 如果下标是奇数，则该位置表达的是三角形
            is_triangle = (i % 2 == 1)
            # 用大致比例分割三角形数量
            # cut_off_index = int(lowest_index / k_count)
            # if i > cut_off_index:
            #     max_length = (k_count - lowest_index)
            # else:
            #     max_length = lowest_index

            if is_triangle:
                # 单个长度判断
                if combination[i] + step > k_count:
                    combination[i] = init_value
                    i -= 1
                    continue

                # 三角形长度只能是0或初始值
                if combination[i] == 0:
                    combination[i] = min_length
                else:
                    combination[i] += step
                
                # 总长剪枝
                # if i > cut_off_index:
                #     is_over_max = sum(combination[i:]) > max_length
                # else:
                #     is_over_max = sum(combination[:i]) > max_length
                is_over_max = sum(combination) > k_count
                
                # 各种剪枝逻辑
                is_intersect = is_over_k_line(combination, i)  # 相交剪枝
                if is_over_max or is_intersect:
                    combination[i] = init_value
                    i -= 1
                else:
                    break
            else:
                # 单个长度判断
                if combination[i] + space_step > space_max:
                    combination[i] = 0
                    i -= 1
                    continue

                combination[i] += space_step

                # 总长剪枝
                # if i > cut_off_index:
                #     is_over_max = sum(combination[i:]) > max_length
                # else:
                #     is_over_max = sum(combination[:i]) > max_length
                # is_over_max = is_over_max or sum(combination) > k_count
                is_over_max = sum(combination) > k_count
                if is_over_max:
                    combination[i] = 0
                    i -= 1
                else:
                    break

        # If i < 0, we've exhausted all combinations
        if i < 0:
            break

    return count


if __name__ == '__main__':
    # Generate all 8-digit combinations
    MAX_TRIANGLE_COUNT = 5
    K_COUNT = 100
    STEP = 10
    MIN_TRIANGLE_BOTTOM_LENGTH = 13

    # 生成high
    high = [800]
    highest = high[0]
    highest_index = 0
    for i1 in range(K_COUNT - 1):
        # 生成一个[-10, 10]之间的随机数
        distance = random.randint(-30, 30)
        num = high[-1] + distance
        # 添加新的元素到数组中
        if highest < num:
            highest_index = i1 + 1
            highest = num
        high.append(num)

    # 生成low
    low = []
    lowest = 999999999
    lowest_index = -1
    for i2 in range(K_COUNT):
        # 生成一个[-10, -1]之间的随机数
        distance = random.randint(-20, -1)
        num = high[i2] + distance
        if lowest > num:
            lowest_index = i2
            lowest = num
        # 添加新的元素到数组中
        low.append(num)

    # print(high)
    # print(low)

    print(generate_combinations(MAX_TRIANGLE_COUNT, K_COUNT, STEP, MIN_TRIANGLE_BOTTOM_LENGTH, 0))
    print('lowest=', lowest, 'lowest_index=', lowest_index)
    # print(is_over_k_line([2, 23, 0, 33, 4, 5, 4], 5))