max points on a line

max points on a line

This problem looks so hard.But, it seems that I have seen this some where before. Two monthes before, when we take part in the ACM campus of BUPT, There was a problem looks like this.It was asking that Is there an three points on a same line?

How to resolve these two questions?

These two problems looks different. But actually they are almost same qusetions. While one is asking you to figure out the existance, the other one is asking you to figure out the maxnum.

Solve the easy one first

Obviously, the existance one question is easy. Two points could determine a line, and we just need to find out is there a line appears two or more times. Hashtable is quite suit for this problems. And this problem is resolved.

Harder one seems no longer harder

Come back to this question, it could be resolved by hashtables too. And we need to enumerate each point. For this point put the lines formed with other point into a hashtable, and get the maxnum.

someting mistake I have made

  • There are duplicate points.
  • Do not forget add the point itself.
  • If two line have the same one point, only the k(y=kx+b) is the important thing.
  • The max of double in CPP is 1.79769e+308
  • At the begining, I save every points in the hashtable, this is really suck.

code of CPP

 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     int maxPoints(vector<Point> &points) {
13         int n = points.size();
14         if ( n == 0 ) {
15             return 0;
16         }
17         map < double , int > kMap;
18         kMap.clear();
19         int result = 0;
20         int same = 0;
21         for ( int i = 0; i < n; i++ ) {
22             same = 0;
23             int count = 0;
24             kMap.clear();
25             for ( int j = 0; j < n; j++ ) {
26                 if ( samePoint(points[i],points[j]) ) {
27                     same++;
28                     continue;
29                 }
30                 double k = getK(points[i],points[j]);
31                 kMap[k] += 1;
32                 count = max(count,kMap[k]);
33             }
34             result = max(result,count+same);
35         }
36         return result;
37     }
38     
39     bool samePoint( Point p1, Point p2 ) {
40         return p1.x == p2.x && p1.y == p2.y;
41     }
42     
43     double getK( Point p1, Point p2 ) {
44         double x = p1.x-p2.x;
45         double y = p1.y-p2.y;
46         if ( x == 0 ) {
47             return 1.79769e+308;
48         }
49         return y/x;
50     }
51 };

Loading Disqus comments...
Table of Contents