int main() { int points[N][2]={{0,0},{1,1},{2,2},{2,10},{2,6}}; set::iterator it; int i,j,k; Line l; for (i=0; ifor (j=i+1; jif(points[i][0]!=points[j][0]){ creatline(l,points[i],points[j]); it = myset.find(l); if (it!=myset.end()) //we've seen this line before continue;
cout << "("<cout << ", ("< for (k=0; kif (k!=i && k!=j && points[k][1]==((l.a)*points[k][0]+l. b)) { cout << ", ("<} }cout << endl; myset.insert(l); } else { l=Line(0xFFFFFFFF,points[i][0]); //now a is infinity, b represent the x-axis value it = myset.find(l); if (it!=myset.end()) continue; cout << "("<cout << ", ("< for (k=0; kif (k!=i && k!=j && points[k][0]==points[i][0]) { cout << ", ("< } }cout << endl; myset.insert(l); } } } cout << myset.size() << " lines in total."<}
The time complexity is O(n^3), not n^2. for each pair of points (n^2), you have to check with the rest of the points (n). so total O(n^3). Don't know whether there is any algo can do better than this though.
I just got an idea with n*n*logn time complexity: Pair wise get all slope and intersection to X axis. This is n*n, resulting in n*n pairs. Sort the n*n pairs to find the same ones (on same line), n*n*log(n*n) => n*n *logn. So the final complex is n*n*logn.
【在 d****2 的大作中提到】 : The time complexity is O(n^3), not n^2. for each pair of points (n^2), you : have to check with the rest of the points (n). so total O(n^3). Don't know : whether there is any algo can do better than this though.