w********s
发帖数: 1570 | 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;
} | p***e
发帖数: 111 | 2 这道题还能用dp? 用排序是nlogn, 用dp有线性的解法?
【在 w********s 的大作中提到】
: 我试过人家什么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;
:
| w********s
发帖数: 1570 | 3 没有线性解法，dp还是n^2的，但比n^3看上去好，但实际上也不快。
hashmap和浮点都是要花不少时间的。
【在 p***e 的大作中提到】
: 这道题还能用dp? 用排序是nlogn, 用dp有线性的解法?
| w********s
发帖数: 1570 | 4 排序是n^2logn
【在 p***e 的大作中提到】
: 这道题还能用dp? 用排序是nlogn, 用dp有线性的解法?
| p***e
发帖数: 111 | 5 谢谢指出. 我记错了。
【在 w********s 的大作中提到】
: 排序是n^2logn
|
|
