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 ;
}

最新文章

  1. IE的F12开发人员工具不显示问题
  2. WiFi流量劫持—— JS脚本缓存投毒
  3. opencv_haar分类器的训练
  4. bootstrap 水平表单
  5. IIS下打印报表到Excel
  6. python 逐行读取文件的三种方法
  7. java 抽象类和接口的区别
  8. SharePoint 2010 master page 控件介绍(5):其他
  9. 初用jquery
  10. NSString截取文件名(很笨的方法)
  11. Spring:利用PerformanceMonitorInterceptor来协助应用性能优化
  12. php Yii2图片的url自动加localhost
  13. js eval函数写一个简单的计算器
  14. jquery.form.js 实现异步上传
  15. python的数据相关框架
  16. Mockito/PowerMockito Straige Issues
  17. 安装cacti
  18. 【maven】Maven根据Profile读取不同配置环境配置文件
  19. java的关键字:static、final
  20. poj 3468 A Simple Problem with Integers 线段树区间加,区间查询和(模板)

热门文章

  1. Django TypeError: isinstance() arg 2 must be a type or tuple of types
  2. 制作根文件系统之Busybox init进程的启动过程分析
  3. c# 子线程打开子窗体
  4. p值还是 FDR ?
  5. P3587 [POI2015]POD
  6. 20172306《Java程序设计与数据结构》第九周学习总结
  7. VS2010下MFC的串口编程
  8. Ubuntu12.04软件安装指南
  9. 超详细的PS抠图方法
  10. jQuery操作(一)