s*****y
发帖数: 897 | 1 1.10 Given a two dimensional graph with 6000 points on it, find a line which
passes the most number of points.
Basic Idea: We need two points to define a line. So, for all possible lines,
check which has the max number of points passing though. Let’s say there
are N points, and P is the set of all points.
Algorithm:
Lmax = 0, Maxp=0 for all pairs of point (Pi,Pj) in P
calculate number of points m passing through the line L(P1,Pj) if (m > Maxp)
{
Maxp = m; Lmax = L(Pi,Pj);
} return Lmax;
Time complexity is O(N^3) because calculating the number of points on the
query line is yet another pass through the set.
看不懂答案，有懂的可以说说吗？ 谢谢。 |
|
