Skip to content

Instantly share code, notes, and snippets.

@kanrourou
Created November 6, 2017 00:31
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
struct Fraction
{
long sign, above, below;
Fraction(long numerator, long denominator)
{
sign = (numerator < 0) ^ (denominator < 0)? -1: 1;
above = abs(numerator);
below = abs(denominator);
}
};
bool operator==(const Fraction& f1, const Fraction& f2)
{
return f1.sign == f2.sign && f1.above == f2.above && f1.below == f2.below;
}
struct hashFraction
{
size_t operator()(const Fraction& f) const
{
string sign = f.sign == 1? "": "-";
string str = sign + to_string(f.above) + "/" + to_string(f.below);
return std::hash<string>{}(str);
}
};
class Solution {
public:
int maxPoints(vector<Point>& points) {
int len = points.size(), res = 0;
for(int i = 0; i < len; ++i)
{
unordered_map<Fraction, int, hashFraction> map;
int dup = 1, currMax = 0;
for(int j = 0; j < len; ++j)
{
if(j == i)continue;
long y = (long)points[j].y - (long)points[i].y, x = (long)points[j].x - (long)points[i].x;
if(!x && !y)
++dup;
else
{
long div = gcd(y, x);
Fraction f(y / div, x / div);
++map[f];
currMax = max(currMax, map[f]);
}
}
res = max(res, currMax + dup);
}
return res;
}
private:
long gcd(long a, long b)
{
a = abs(a);
b = abs(b);
if(a < b)return gcd(b, a);
if(!b)return a;
return gcd(b, a % b);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment