西安网站建设设计的好公司排名百度关键词热搜

题目：（直线）

题目描述（12届 C&C++ B组C题）

解题思路：

1. 题目理解:

   • 在平面直角坐标系中，从给定的点集中确定唯一的直线。

   • 两点确定一条直线，判断两条直线是否相同，可通过它们的斜率 aaa 和截距 bbb 进行唯一标识。

2. 优化判断:

   • 直线的唯一性可通过公式计算得到斜率 和截距

   • 对每一对点，判断是否出现过相同的 (a,b)，如果没有，存储下来。

3. 特殊情况:

   • 垂直线（即 x1=x2）和水平线（即 y1=y2​）需要单独处理。

4. 复杂度:

   • 遍历所有点对的组合，时间复杂度为 O(n^2)，其中 n 为点的数量。题目给出的范围使得暴力解法可行。

代码实现（C语言）：

#include <stdio.h>int n = 0;
double ab[100000][2] = {{0}, {0}};int fun(int x0, int y0, int x1, int y1) {double a = (y0 - y1) * 1.0 / (x0 - x1);double b = (x0 * y1 - x1 * y0) * 1.0 / (x0 - x1);for (int i = 0; i < n; i++) {if (ab[i][0] == a && ab[i][1] == b) return 0;}ab[n][0] = a;ab[n][1] = b;n++;return 1;
}int main() {for (int x0 = 0; x0 < 20; x0++) {for (int y0 = 0; y0 < 21; y0++) {for (int x1 = x0 + 1; x1 < 20; x1++) {for (int y1 = y0 + 1; y1 < 21; y1++) {fun(x0, y0, x1, y1);}}}}printf("%d\n", 2 * n + 41); // 2*n 是对称直线，+41 是坐标轴垂直线return 0;
}

得到运行结果：

难度分析

⭐️⭐️⭐️

总结

通过代数几何知识（斜率与截距）解决几何问题是本题的核心思路，利用两层嵌套循环枚举点对，函数封装了检查与存储逻辑，代码结构紧凑。