20×21整点网格直线计数之谜(2021年十二届蓝桥杯CC++软件赛省赛 B组)

问题描述：

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
给定平面上2×3个整点{(x,y)|0≤x<2,0≤y<3,xEZ,yEZ}，即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点一共确定了11条不同的直线。
给定平面上20×21个整点{(x,y)|0≤x<20,0≤y<21,xEz, yEZ}，即横坐标是0到19(包含0和19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。请问这些点一共确定了多少条不同的直线。

直线的一般式为Ax + By + C = 0，其中A、B、C是整数，且满足：

一.A、B不同时为0

二.A、B、C的最大公约数（GCD）为1（即最简形式）

三.符号规则：A≥0；若A=0，则B≥0

为什么用一般式？

一.能表示所有直线（包括垂直于x轴的直线）
二.用整数表示，避免浮点数精度问题
三.同一直线的一般式唯一，不会出现多种表示方式

斜截式（有局限性）

一.斜截式为y = kx + b，其中k是斜率，b是截距。但：

二.垂直于x轴的直线（x=a）无法用斜截式表示

三.斜率k和截距b可能是无限小数，存储和比较会有精度问题

给定两点P1(x1, y1)和P2(x2, y2)，如何计算直线的一般式？

1. 向量法推导

向量P1P2 = (x2-x1, y2-y1)，直线的法向量为(A, B)，满足法向量与P1P2垂直，即：

A*(x2-x1) + B*(y2-y1) = 0

取A = y2 - y1，B = x1 - x2，则满足垂直条件。再代入点P1的坐标，可得：

C = -(A*x1 + B*y1) = x2*y1 - x1*y2

最终直线的一般式为：

(y2 - y1)x + (x1 - x2)y + (x2*y1 - x1*y2) = 0

直接计算得到的一般式可能不是最简形式，也可能有不同的符号，需要标准化处理：

1. 约分：除以最大公约数
计算A、B、C的最大公约数GCD，然后将A、B、C分别除以GCD：

g = GCD(GCD(|A|, |B|), |C|)
A' = A / g
B' = B / g
C' = C / g
示例：4x + 6y + 8 = 0，GCD(4,6,8)=2，标准化后为 2x + 3y + 4 = 0

2. 统一符号：确保表示一致
如果A' > 0：保持不变
如果A' < 0：将A'、B'、C'同时乘以-1，使得A'≥0
如果A' = 0：确保B' > 0（如果B' < 0，将B'、C'同时乘以-1）

示例：-2x + 4y - 6 = 0，A'=-2<0，乘以-1后为 2x - 4y + 6 = 0，再约分得到 x - 2y + 3 = 0

1. 遍历所有点对的优化
20×21个整点共有420个点，总点对数量为 C(420,2) = 87990对

除了斜线，还有两类特殊直线可以单独统计：

1. 垂直线（x = a）

共有20条，a从0到19。一般式为1x + 0y - a = 0，标准化后为(1, 0, -a)

2. 水平线（y = b）

共有21条，b从0到20。一般式为0x + 1y - b = 0，标准化后为(0, 1, -b)