python解法蚂蚁开会

解题思路:

如果两条线段共线，计算它们的交集部分，并生成所有整点。

计算两条线段的交点，检查交点是否为整点且在线段范围内。

使用集合存储所有符合条件的整点，最后输出集合的大小。

注意事项:

在计算交点时，浮点数精度可能导致误差，因此需要判断交点是否为整点时，使用四舍五入并检查误差范围。

共线线段需要特别处理，计算它们的交集部分，并生成所有整点。

确保交点在两条线段的范围内，避免计算无效的交点。

参考代码:

import sys

import math

def readints():

    """读取一行输入并转换为整数列表"""

    return list(map(int, sys.stdin.readline().split()))

n = int(sys.stdin.readline())  # 读取线段数量

segments = []  # 存储所有线段的端点

for _ in range(n):

    x1, y1, x2, y2 = readints()  # 读取每条线段的两个端点

    segments.append(((x1, y1), (x2, y2)))

points = set()  # 使用集合存储所有符合条件的整点

for i in range(n):

    for j in range(i+1, n):

        (A, B) = segments[i]  # 第一条线段的两个端点

        (C, D) = segments[j]  # 第二条线段的两个端点

        x1, y1 = A

        x2, y2 = B

        x3, y3 = C

        x4, y4 = D

        dx1 = x2 - x1  # 第一条线段的x方向增量

        dy1 = y2 - y1  # 第一条线段的y方向增量

        # 计算第二条线段的两个端点相对于第一条线段的位置

        cross_c = dx1 * (y3 - y1) - dy1 * (x3 - x1)

        cross_d = dx1 * (y4 - y1) - dy1 * (x4 - x1)

        # 如果两条线段共线

        if cross_c == 0 and cross_d == 0:

            denom = dx1 * dx1 + dy1 * dy1  # 分母，用于计算参数t

            if denom == 0:

                continue  # 如果线段长度为0，跳过

            # 计算第二条线段的两个端点在第一条线段上的参数t

            t_c_numer = (x3 - x1) * dx1 + (y3 - y1) * dy1

            t_c = t_c_numer / denom

            t_d_numer = (x4 - x1) * dx1 + (y4 - y1) * dy1

            t_d = t_d_numer / denom

            # 计算两条线段的交集部分的参数范围

            t_start = max(0.0, min(t_c, t_d))

            t_end = min(1.0, max(t_c, t_d))

            if t_start > t_end:

                continue  # 如果没有交集，跳过

            # 计算交集部分的起点和终点坐标

            px = x1 + dx1 * t_start

            py = y1 + dy1 * t_start

            qx = x1 + dx1 * t_end

            qy = y1 + dy1 * t_end

            # 将坐标四舍五入为整数

            px_int = int(round(px))

            py_int = int(round(py))

            qx_int = int(round(qx))

            qy_int = int(round(qy))

            # 检查四舍五入后的坐标是否与原始坐标接近

            if abs(px - px_int) > 1e-6 or abs(py - py_int) > 1e-6:

                continue

            if abs(qx - qx_int) > 1e-6 or abs(qy - qy_int) > 1e-6:

                continue

            px = px_int

            py = py_int

            qx = qx_int

            qy = qy_int

            # 计算交集线段的增量

            dx = qx - px

            dy = qy - py

            # 如果交集线段长度为0，直接添加点

            if dx == 0 and dy == 0:

                points.add((px, py))

                continue

            # 计算增量方向的最小单位向量

            g = math.gcd(abs(dx), abs(dy))

            a = dx // g

            b = dy // g

            # 生成所有整点

            for k in range(g + 1):

                x = px + a * k

                y = py + b * k

                points.add((x, y))

        else:

            # 计算两条线段的交点

            D = (x2 - x1) * (y3 - y4) - (x3 - x4) * (y2 - y1)

            if D == 0:

                continue  # 如果两条线段平行，跳过

            # 计算交点的参数t和s

            numerator_t = (x3 - x1) * (y3 - y4) - (x3 - x4) * (y3 - y1)

            numerator_s = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

            t = numerator_t / D

            s = numerator_s / D

            # 检查交点是否在两条线段的范围内

            if t < 0 or t > 1 or s < 0 or s > 1:

                continue

            # 计算交点的坐标

            x_num = x1 * D + numerator_t * (x2 - x1)

            y_num = y1 * D + numerator_t * (y2 - y1)

            # 检查交点是否为整点

            if x_num % D != 0 or y_num % D != 0:

                continue

            x = x_num // D

            y = y_num // D

            # 添加交点到集合中

            points.add((x, y))

print(len(points))  # 输出所有符合条件的整点数量