[H枚举]lc149.直线上最多的点数(枚举+细节优化+数学)

1. 题目来源

链接&＃xff1a;149. 直线上最多的点数

大佬题解&＃xff1a;直线一般式&＃xff0c;C&＃43;&＃43; STL 应用

2. 题目解析

枚举&＃43;算法优化。

暴力做法&＃xff1a;

• 枚举直线&＃xff0c;两点确定一条直线&＃xff0c;O(n2)O(n^2)O(n2)。
• 针对每个直线&＃xff0c;确定直线上有多少点&＃xff0c;直接套直线方程即可&＃xff0c;$O(n)$。
• 总的时间是 O(n3)O(n^3)O(n3)。

优化做法&＃xff1a;

• 不先将所有直线枚举出来&＃xff0c;而只枚举直线上的一个点&＃xff0c;称为中心点。
• 那么经过这个点的直线是 360° 任意多条的。
• 然后再枚举其他各点。
• 当枚举另一个点时有两种情况&＃xff1a;
  • 它与中心点构成一条新的直线&＃xff0c;则保存该直线的斜率即可&＃xff0c;用于判断之后的其它点是否在该直线上。
  • 它与中心点构成的直线已经出现过&＃xff0c;即斜率相等&＃xff0c;则在该直线上加上这个点的数量即可。
• 任意一点都可能成为中心点&＃xff0c;通过枚举其它各点与中心点的连线&＃xff0c;我们可以得到所有的直线。每次即可求得当前中心点所在直线的最大点数数量。
• 先枚举中心点&＃xff0c;再枚举其余各点。故这个的复杂度是 O(n2)O(n^2)O(n2) 的。

细节&＃xff1a;

• 针对直线的表示&＃xff0c;在此直接使用斜截式表示即可&＃xff0c;注意小数精度问题。
• 斜截式求斜率时&＃xff0c;分母为零情况注意&＃xff0c;即垂线情况&＃xff0c;需要单独用变量纪录这条直线。
• 如果某点与中心点重叠&＃xff0c;则该点会落到所有直线上&＃xff0c;需要单独使用变量记录和中心点重叠的点数。
• 则最终统计哪条直线点数最多时&＃xff0c;需要统计比较正常直线上的点数、垂线上的点数&＃xff0c;最后再加上和中心点重叠的点数。
• 本题精度要求较高&＃xff0c;需要使用 long double。

关于使用两点式和斜截式&＃xff1a;

• 两点式不需要讨论分母为 0 的这种垂线情况&＃xff0c;将直线可以直接化为一般式&＃xff0c;以下是我一些总结&＃xff1a;
  
• 尤其注意两点式的变形情况&＃xff0c;这个方程就不涉及分母为 0 的情况了。简单整理可以得到直线的一般式&＃xff1a;Ax&＃43;By&＃43;C&＃61;0等价于x(y2−y1)&＃43;y(x1−x2)&＃43;x1(y1−y2)&＃43;y1(x2−x1)&＃61;0Ax&＃43;By&＃43;C&＃61;0 等价于 x(y_2-y_1)&＃43;y(x_1-x_2)&＃43;x_1(y_1-y_2)&＃43;y_1(x_2-x_1)&＃61;0Ax&＃43;By&＃43;C&＃61;0等价于x(y2​−y1​)&＃43;y(x1​−x2​)&＃43;x1​(y1​−y2​)&＃43;y1​(x2​−x1​)&＃61;0
  其可以与平面上的直线一一对应&＃xff0c;但是不同的 $A,B,C$ 可能存在倍数关系&＃xff0c;即可能出现直线共线的情况。所以需要对 $A,B,C$ 约掉其最大公约数&＃xff0c;保证直线唯一。

极其优质&＃xff1a;

• 直线一般式&＃xff0c;C&＃43;&＃43; STL 应用
• 实际上只需要一般式中的 A、B 即可表示一个直线

当使用 unordered_map 时&＃xff0c;需要自己传入 hash 函数。

时间复杂度&＃xff1a;O(n2)O(n^2)O(n2)
空间复杂度&＃xff1a;$O(n)$

class Solution {
public:int maxPoints(vector<vector<int>>& points) {typedef long double LD;int res &＃61; 0;for (auto p : points) {int s1 &＃61; 0, s2 &＃61; 0; // s1 和中心点相同&＃xff0c;s2 直线unordered_map<LD, int> cnt;for (auto q : points) {if (p &＃61;&＃61; q) s1 &＃43;&＃43; ;else if (q[0] &＃61;&＃61; p[0]) s2 &＃43;&＃43; ;else {LD k &＃61; (LD)(q[1] - p[1]) / (q[0] - p[0]);cnt[k] &＃43;&＃43; ;}}int c &＃61; s2;for (auto [k, v] : cnt) c &＃61; max(v, c);res &＃61; max(res, c &＃43; s1);}return res;}
};


大佬的写法&＃xff1a;

用 array 用 tuple 均可。类似于这种类型、pair 等均需要自己传入哈希函数。

// 计算三元组的哈希值
struct v3_hash {size_t operator()(const array<int, 3> &x) const {return x[0] ^ x[1] ^ ((size_t)x[2] << 32);}
};class Solution {
public:int maxPoints(vector<vector<int>>& points) {// Ax &＃43; By &＃43; C &＃61; 0, (A, B, C)// A(x1 - x2) &＃43; B(y1 - y2) &＃61; 0// (A, B, C) &＃61; (y2 - y1, x1 - x2, x2 * y1 - x1 * y2)int best &＃61; 0;for (int i &＃61; 0; i < points.size(); &＃43;&＃43;i) {// 记录同一条直线的出现次数unordered_map<array<int, 3>, int, v3_hash> cnts;const int x1 &＃61; points[i][0];const int y1 &＃61; points[i][1];for (int j &＃61; i &＃43; 1; j < points.size(); &＃43;&＃43;j) {const int x2 &＃61; points[j][0];const int y2 &＃61; points[j][1];// 计算表示一条直线的三元组array<int, 3> v3 &＃61; {y2 - y1, x1 - x2, x2 * y1 - x1 * y2};bool first_non_zero &＃61; true; // 判断是否遇到第一个非零元素bool minus &＃61; false; // 记录三元组第一个非零元素是否为负数int g &＃61; 0; // 变量g记录最大公约数for (int k &＃61; 0; k < 3; &＃43;&＃43;k) {if (v3[k] !&＃61; 0) {if (first_non_zero) {first_non_zero &＃61; false;minus &＃61; v3[k] < 0;g &＃61; abs(v3[k]);} else {g &＃61; __gcd(g, abs(v3[k]));}}}// 对三元组进行约分if (g !&＃61; 0) {if (minus) g &＃61; -g;for (int k &＃61; 0; k < 3; &＃43;&＃43;k) {if (v3[k] !&＃61; 0) v3[k] /&＃61; g;}}best &＃61; max(best, &＃43;&＃43;cnts[v3]);}}// 直线上最多的点数 &＃61; 同一条直线出现的最大次数 &＃43; 1return best &＃43; 1;}
};


简单优化&＃xff0c;在此题目保证了各点互不相同&＃xff0c;则 gcd() 一定不为 0&＃xff0c;不会出现除 0 错误&＃xff0c;则对 A、B、C 求最大公约数除了就行了&＃xff0c;但是会不会差一个符号呢&＃xff1f;

其实可能是会的&＃xff0c;__gcd 是忽略符号的&＃xff0c;即 __gcd(-2, -6)&＃61;-2&＃xff0c;则正号依旧是正号&＃xff0c;负号依旧是负号&＃xff0c;若 &＃43; - &＃43; &＃61; 0、- &＃43; - &＃61; 0&＃xff0c;那么 gcd 后两者符号刚好交换&＃xff0c;等价于两条直线了&＃xff0c;但在本题貌似没有出现这个情况。

不知道能否严格证明该情况不会出现。 或是这次对了只是侥幸&＃xff1f;

struct v3_hash {size_t operator()(const array<int, 3> &x) const {return x[0] ^ x[1] ^ ((size_t)x[2] << 32);}
};class Solution {
public:int maxPoints(vector<vector<int>>& points) {int best &＃61; 0;for (int i &＃61; 0; i < points.size(); &＃43;&＃43;i) {unordered_map<array<int, 3>, int, v3_hash> cnts;const int x1 &＃61; points[i][0];const int y1 &＃61; points[i][1];for (int j &＃61; i &＃43; 1; j < points.size(); &＃43;&＃43;j) {const int x2 &＃61; points[j][0];const int y2 &＃61; points[j][1];// 计算表示一条直线的三元组int A &＃61; y2 - y1, B &＃61; x1 - x2, C &＃61; x2 * y1 - x1 * y2;int t &＃61; __gcd(__gcd(A, B), __gcd(B, C));A /&＃61; t, B /&＃61; t, C /&＃61; t; // 直接化简array<int, 3> v3 &＃61; {A, B, C};best &＃61; max(best, &＃43;&＃43;cnts[v3]);}}return best &＃43; 1;}
};