# Share an idea with you : )

• This idea comes from a homework from Coursera Algorithm Princeton.

Basically, first calculate slops for a given point, then do a sort, and then find the maximum length with consecutive same value.

Be careful with vertical lines and those points that are same with the given point.

``````class Solution {
public:
int maxPoints(vector<Point>& points)
{
int maxLength = 0;
for (int i = 0; i < points.size(); ++i)
{
std::vector<double> slops;
int same = 0;
int vertical = 0;

for (int j = 0; j < points.size(); ++j)
{
if (points[i].x == points[j].x && points[i].y == points[j].y)
same++;
else if (points[i].x == points[j].x)
vertical++;
else
{
double slop = (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x);
slops.push_back(slop);
}
}

sort(slops.begin(), slops.end());

// normal points
int currentMax = 0;
int strike = slops.size() > 0 ? 1 : 0;
for (int i = 1; i < slops.size(); ++i)
{
if (slops[i] == slops[i - 1])
strike++;
else
{
currentMax = max(currentMax, strike);
strike = 1;
}
}
currentMax = max(currentMax, strike);

// vertical points
currentMax = max(currentMax, vertical) + same;

// max
maxLength = max(maxLength, currentMax);
}

return maxLength;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.