Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Max Points on a Line-2014.01.05

Posted on 2014-01-11 01:54 Uriel 阅读(125) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
这题POJ上有原题,平面上一堆点,求最多共线点数,方法不难,1~n枚举所有点,求它和其他点分别构成直线的斜率,然后sort,然后算有几个相同斜率的,求个max
这题的trick在于有重复点,为了处理这个搞了半天【我太挫...然后用的是很Naive的办法,重复点单独计数单独算,另外斜率不存在的时候设为一个很大的数(1e10)

 1 /**
 2  * Definition for a point.
 3  * struct Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() : x(0), y(0) {}
 7  *     Point(int a, int b) : x(a), y(b) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     struct pt{
13         double k;
14         int fg;
15         bool operator<(const pt &m)const {
16             return k < m.k;
17         }
18     }pp[1010];
19     int maxPoints(vector<Point> &points) {
20         int max = 0, pre_max = 0;
21         int cnt = points.size();
22         for(int i = 0; i < cnt; ++i) {
23             int nt = 0, nnt = 0;
24             for(int j = i; j < cnt; ++j) {
25                 if((points[j].x - points[i].x) < -1e-6 || (points[j].x - points[i].x) > 1e-6) {
26                     pp[j].k = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
27                     pp[j].fg = 0;
28                 }
29                 else if((points[j].x - points[i].x) > -1e-6 && (points[j].x - points[i].x) < 1e-6 && (points[j].y - points[i].y) > -1e-6 && (points[j].y - points[i].y) < 1e-6) {
30                     pp[j].fg = 1;
31                     nnt++;
32                 }
33                 else {
34                     pp[j].k = 1e10;
35                     pp[j].fg = 0;
36                 }
37             }
38             sort(pp + i + 1, pp + cnt);
39             for(int j = i + 2; j < cnt; ++j) {
40                 if(pp[j].fg) continue;
41                 else {
42                     if(!nt) nt = 1;
43                     if(pp[j - 1].k == pp[j].k) nt++;
44                     else {
45                         if(nt + nnt> max) max = nt + nnt;
46                         nt = 1;
47                     }
48                 }
49             }
50             if(nt + nnt> max) max = nt + nnt;
51             if(nnt < cnt - i && nnt + 1 > max) max = nnt + 1;
52         }
53         if(cnt > 2)
54             return max;
55         else
56             return cnt;
57     }
58 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理