leetcode-[3]Max Points on a Line
2024-10-19 06:18:54
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
思路:最多的点,必然是点连成线时,所有斜率相同的最多的组合情况;
那么如果不在同一直线点的组合也可能斜率相同,找其中一点与其它点连即可。
#include <iostream>
#include <vector>
#include <map> using namespace std; struct Point {
int x;
int y;
Point(): x(), y() {}
Point(int a, int b): x(a), y(b) {}
}; class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size() < )
return points.size(); int result = ;
for (int i = ; i < points.size(); i++) {
map<pair<int, int>, int> line; int overlap = , vertical = , curMax = ;
for (int j = i + ; j < points.size(); j++) {
if((points[i].x == points[j].x) &&
(points[i].y == points[j].y)) {
overlap ++;
continue;
}
else if (points[i].x == points[j].x) {
vertical ++;
}
else {
int dx = points[i].x - points[j].x;
int dy = points[i].y - points[j].y; int gcd = GCD(dx, dy); dx /= gcd;
dy /= gcd; line[make_pair(dx, dy)]++;
curMax = max(line[make_pair(dx, dy)], curMax);
}
curMax = max(vertical, curMax);
}
result = max(result, curMax+overlap+);
}
return result;
} int GCD(int a, int b) {
if (b == )
return a;
return GCD(b, a%b);
}
}; int main() {
vector<Point> points; points.push_back(Point(, ));
points.push_back(Point(, ));
points.push_back(Point(, ));
Solution *solution = new Solution();
cout << solution->maxPoints(points) << endl; // (3,10),(0,2),(0,2),(3,10)
vector<Point> points2;
points2.push_back(Point(, ));
points2.push_back(Point(, ));
points2.push_back(Point(, ));
points2.push_back(Point(, ));
cout << solution->maxPoints(points2) << endl; return ;
}
最新文章
- IE的F12开发人员工具不显示问题
- WiFi流量劫持—— JS脚本缓存投毒
- opencv_haar分类器的训练
- bootstrap 水平表单
- IIS下打印报表到Excel
- python 逐行读取文件的三种方法
- java 抽象类和接口的区别
- SharePoint 2010 master page 控件介绍(5):其他
- 初用jquery
- NSString截取文件名(很笨的方法)
- Spring:利用PerformanceMonitorInterceptor来协助应用性能优化
- php Yii2图片的url自动加localhost
- js eval函数写一个简单的计算器
- jquery.form.js 实现异步上传
- python的数据相关框架
- Mockito/PowerMockito Straige Issues
- 安装cacti
- 【maven】Maven根据Profile读取不同配置环境配置文件
- java的关键字:static、final
- poj 3468 A Simple Problem with Integers 线段树区间加,区间查询和(模板)