2014-03-20 02:24

题目:给定二位平面上一堆点,找到一条直线,使其穿过的点数量最多。

解法:我的解法只能适用整点,对于实数坐标就得换效率更低的办法了。请参见LeetCode - Max Points on a Line - zhuli19901106 - 博客园

代码:

 // 7.6 Find the line that crosses the most points.
#include <unordered_map>
#include <vector>
using namespace std; struct Point {
int x;
int y;
Point() : x(), y() {}
Point(int a, int b) : x(a), y(b) {}
}; struct st {
int x;
int y;
st(int _x = , int _y = ): x(_x), y(_y) {}; bool operator == (const st &other) const {
return x == other.x && y == other.y;
}; bool operator != (const st &other) const {
return x != other.x || y != other.y;
};
}; struct line {
// ax + by + c = 0;
int a;
int b;
int c;
line(int _a = , int _b = , int _c = ): a(_a), b(_b), c(_c) {};
}; struct hash_functor {
size_t operator () (const st &a) const {
return (a.x * + a.y);
}
}; struct compare_functor {
bool operator () (const st &a, const st &b) const {
return (a.x == b.x && a.y == b.y);
}
}; typedef unordered_map<st, int, hash_functor, compare_functor> st_map; class Solution {
public:
int maxPoints(vector<Point> &points, line &result_line) {
int n = (int)points.size(); if (n <= ) {
return n;
} st_map um;
st tmp;
// special tangent value for duplicate points
st dup(, ); int i, j;
st_map::const_iterator umit;
int dup_count;
int max_count;
int result = ;
for (i = ; i < n; ++i) {
for (j = i + ; j < n; ++j) {
tmp.x = points[j].x - points[i].x;
tmp.y = points[j].y - points[i].y;
// make sure one tangent value has one representation only.
normalize(tmp);
if (um.find(tmp) != um.end()) {
++um[tmp];
} else {
um[tmp] = ;
}
}
max_count = dup_count = ;
for (umit = um.begin(); umit != um.end(); ++umit) {
if (umit->first != dup) {
if (umit->second > max_count) {
max_count = umit->second;
getLine(umit->first, points[i], result_line);
}
} else {
dup_count = umit->second;
}
}
max_count = max_count + dup_count + ;
result = (max_count > result ? max_count : result);
um.clear();
} return result;
}
private:
void normalize(st &tmp) {
if (tmp.x == && tmp.y == ) {
// (0, 0)
return;
}
if (tmp.x == ) {
// (0, 1)
tmp.y = ;
return;
}
if (tmp.y == ) {
// (1, 0)
tmp.x = ;
return;
}
if (tmp.x < ) {
// (-2, 3) and (2, -3) => (2, -3)
tmp.x = -tmp.x;
tmp.y = -tmp.y;
} int gcd_value; gcd_value = (tmp.y > ? gcd(tmp.x, tmp.y) : gcd(tmp.x, -tmp.y));
// (4, -6) and (-30, 45) => (2, -3)
// using a double precision risks in accuracy
// so I did it with a pair
tmp.x /= gcd_value;
tmp.y /= gcd_value;
} int gcd(int x, int y) {
// used for reduction of fraction
return y ? gcd(y, x % y) : x;
} void getLine(st tan, Point p, line &res) {
res.a = tan.y;
res.b = -tan.x;
res.c = -(res.a * p.x + res.b * p.y);
}
}; int main()
{
vector<Point> v;
Solution sol;
int i, n;
Point p;
line res; while (scanf("%d", &n) == ) {
for (i = ; i < n; ++i) {
scanf("%d%d", &p.x, &p.y);
v.push_back(p);
}
sol.maxPoints(v, res);
printf("%d %d %d\n", res.a, res.b, res.c);
v.clear();
} return ;
}

最新文章

  1. php 二维数组按某字段排序
  2. Matlab绘图函数一览
  3. android第二天(项目的组成结构)
  4. Directory.GetCurrentDirectory和Application.StartupPath的区别
  5. Android || IOS录制mp3语音文件方法
  6. Matlab之类型转换
  7. HDU 4968 Improving the GPA
  8. 信号之kill和raise函数
  9. “cvSnakeImage”: 找不到标识符
  10. baidu地图让多个标注出现在最佳视野
  11. nodejs之querystring模块
  12. 调用MediaScannerConnection 发生内存泄露的解决方法
  13. 安装Mediamanager 后Messenger后无法登录
  14. CentOS 7 minimal配置网络连接及net-tools安装
  15. js中的find(),filter(),has()的用法和区别
  16. FastJson遇见的问题或项目实战中优化的问题,看源码都可以解决
  17. President&#39;s Path CodeForces - 416E (最短路,计数)
  18. linux下调试core的命令
  19. tesseract-ocr训练方法
  20. 单独运行shell脚本与crontab运行shell脚本的区别

热门文章

  1. 数据结构与算法分析java——线性表1
  2. percona-toolkit 工具集安装
  3. MYSQL 之SET GLOBAL innodb_buffer_pool_size =n
  4. Centos6.4环境下DNS服务器的搭建
  5. 2017.11.8 面向对象分析与设计(UML)---UML的作用及分类
  6. 2017.10.26 JavaWeb----第五章 JavaBean技术
  7. 安装juicer
  8. python 添加 threadpool
  9. express_webpack自动刷新
  10. CSS 滤镜技巧与细节