Created
November 24, 2013 16:43
-
-
Save zsh-89/7629207 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for a point. | |
* struct Point { | |
* int x; | |
* int y; | |
* Point() : x(0), y(0) {} | |
* Point(int a, int b) : x(a), y(b) {} | |
* }; | |
*/ | |
bool operator<(const Point &p1, const Point &p2) { | |
if (p1.x<p2.x) return true; | |
else if (p1.x==p2.x) return p1.y<p2.y; | |
else return false; | |
} | |
bool operator==(const Point &p1, const Point &p2) { | |
return p1.x==p2.x && p1.y==p2.y; | |
} | |
class Solution { | |
public: | |
struct Line { | |
int a, b, c; | |
Line(int _a=0, int _b=0, int _c=0) : a(_a), b(_b), c(_c) {} | |
bool operator==(const Line &l) const { | |
return a==l.a && b==l.b && c==l.c; | |
} | |
}; | |
struct LineHasher { | |
size_t operator()(const Line &l) const { | |
return 31*31*l.a + 31*l.b + l.c; | |
} | |
}; | |
int gcd(int x, int y) const { | |
if (x<y) return gcd(y, x); | |
if (y==0) return x; | |
else return gcd(y, x%y); | |
} | |
Line solve(const Point &p1, const Point &p2) const { // get the line defined by two different points. | |
Line l; | |
if (p1.x==p2.x) { | |
l.a=1; l.b=0; l.c=-p1.x; | |
} else { | |
l.b=p1.x-p2.x; | |
l.a=(p2.y-p1.y); | |
l.c=-(p2.y-p1.y)*p1.x-(p1.x-p2.x)*p1.y; | |
int gcd1=gcd(abs(l.a), abs(l.b)); | |
int gcd2=gcd(abs(l.b), abs(l.c)); | |
int gcd3=gcd(gcd1, gcd2); | |
l.a/=gcd3; l.b/=gcd3; l.c/=gcd3; | |
if (l.b<0) { | |
l.a*=-1; l.b*=-1; l.c*=-1; | |
} | |
} | |
return l; | |
} | |
int maxPoints(vector<Point> &points) { | |
m_.clear(); int N=points.size(); int max_l=0; | |
sort(points.begin(), points.end()); | |
for (int i=0; i<N;) { | |
int same_count=1; | |
for (int j=i+1; j<N; ++j) { | |
if (points[i]==points[j]) ++same_count; | |
else { | |
Line l=solve(points[i], points[j]); | |
auto it=m_.find(l); | |
if (it!=m_.end() && it->second.first==points[i]) { | |
it->second.second += 1; | |
max_l=max(max_l, it->second.second); | |
} else if (it==m_.end()) { | |
m_[l]=make_pair(points[i], same_count+1); | |
max_l=max(max_l, same_count+1); | |
} | |
} | |
} | |
max_l=max(max_l, same_count); | |
i+=same_count; | |
} | |
return max_l; | |
} | |
unordered_map<Line, pair<Point, int>, LineHasher> m_; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This problem really has something worthy to note.
Time complexity
http://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear
According to this article, the problem above is 3-sum hardness, so there are no known solution which is faster than O(N^2).
Implementation
So we just use an hash table and insert C(N, 2) lines into it, than we get the answer, isn't it?
Note that:
So I use ax+by+c=0. and make sure b>=0 && a, b, c are divided by their gcd.
When calculating gcd, note that value of a%b is implementation defined when one of the operand is negative.
For [(0, 0), (0, 0), (1, 1), (1, 1)], the result should be 4.