查询直线的条数

#include iostream#include vector#include set#include numeric // For std::gcdusing namespace std;// 定义点结构struct Point {int x, y;};// 定义直线结构通过最简斜率和直线上的一点来唯一标识// 实际上更好的办法是存储最简方向向量 (dx, dy) 和 经过该方向的最简截距struct Line {int dx, dy, x0, y0;// 重载 运算符以便放入 set 中去重bool operator(const Line other) const {if (dx ! other.dx) return dx other.dx;if (dy ! other.dy) return dy other.dy;if (x0 ! other.x0) return x0 other.x0;return y0 other.y0;}};// 计算最大公约数手动实现或使用 C17 的 std::gcdint gcd(int a, int b) {return b 0 ? a : gcd(b, a % b);}int main() {vectorPoint p;// 1. 生成所有整点for (int i 0; i 20; i) {for (int j 0; j 21; j) {p.push_back({i, j});}}setLine lines;int n p.size();// 2. 遍历所有点对for (int i 0; i n; i) {for (int j i 1; j n; j) {int dx p[i].x - p[j].x;int dy p[i].y - p[j].y;if (dx 0) { // 垂直线lines.insert({0, 1, p[i].x, 0});continue;}if (dy 0) { // 水平线lines.insert({1, 0, 0, p[i].y});continue;}// 通用情况化简斜率int g gcd(abs(dx), abs(dy));dx / g;dy / g;// 规范化方向确保 dx 0if (dx 0) {dx -dx;dy -dy;}/* 唯一标识逻辑直线方程dy * (x - x1) dx * (y - y1)化简为dy * x - dx * y dy * x1 - dx * y1右边项对于同一直线上的所有点是一个常数 C*/int C dy * p[i].x - dx * p[i].y;lines.insert({dx, dy, 0, C});}}// 3. 输出结果cout lines.size() endl;return 0;}