lc里面那个max points O(n3)的算法也不慢啊# JobHunting - 待字闺中
w*s
1 楼
我试过人家什么dp的算法也就比我的n3解法差不多快。
关键是这个虽然是on3，但没有除法，没有浮点，只有整数，速度不慢。
bool online(const Point& p1, const Point& p2, const Point& p3)
{
int dy1 = p2.y - p1.y;
int dy2 = p3.y - p2.y;
int dx1 = p2.x - p1.x;
int dx2 = p3.x - p2.x;
if (dy1 * dx2 == dy2 * dx1) return true;
return false;
}
int maxPoints(vector &points) {
int s = points.size();
if (s < 3) return s;
int max = 1;
for (int i = 0; i < s; ++i)
{
Point& p1 = points[i];
int cntp1 = 1;
for (int j = i + 1; j < s; ++j)
{
Point& p2 = points[j];
if ((p2.x == p1.x) && (p2.y == p1.y))
{
cntp1++;
continue;
}
int cnt = cntp1 + 1;
if (cnt > max) max = cnt;
for (int k = j + 1; k < s; ++k)
{
Point& p3 = points[k];
if (online(p1, p2, p3)) cnt++;
if (cnt > max) max = cnt;
}
}
if (cntp1 > max) max = cntp1;
}
return max;
}
关键是这个虽然是on3，但没有除法，没有浮点，只有整数，速度不慢。
bool online(const Point& p1, const Point& p2, const Point& p3)
{
int dy1 = p2.y - p1.y;
int dy2 = p3.y - p2.y;
int dx1 = p2.x - p1.x;
int dx2 = p3.x - p2.x;
if (dy1 * dx2 == dy2 * dx1) return true;
return false;
}
int maxPoints(vector
int s = points.size();
if (s < 3) return s;
int max = 1;
for (int i = 0; i < s; ++i)
{
Point& p1 = points[i];
int cntp1 = 1;
for (int j = i + 1; j < s; ++j)
{
Point& p2 = points[j];
if ((p2.x == p1.x) && (p2.y == p1.y))
{
cntp1++;
continue;
}
int cnt = cntp1 + 1;
if (cnt > max) max = cnt;
for (int k = j + 1; k < s; ++k)
{
Point& p3 = points[k];
if (online(p1, p2, p3)) cnt++;
if (cnt > max) max = cnt;
}
}
if (cntp1 > max) max = cntp1;
}
return max;
}
