|
|
вернуться в форумI use O(n^3), but i meet time problem. Can you help me? Of course, the best complexity is O(N^2 log N), but O(N^3) can get AC. Can anybody in short explain how to create O(N^2 logN) algorithm, please?
I've already accepted O(n^3) solution and there's no promlem with it(definitely not the best implementation of this algorithm got ac in 0.2 sec), but how to create O(N*NlogN) algo? Use angle sort, after use binary search. I've Accepted O(N*NlogN) :) N^2 * log(N^2) algo:
1) Sort n^2 lines by distance.
2) Iterate from largest to smallest.
3) We have to add line to the answer, if we not have bigger line in set, covering this. We can easily check it with set. O(N^3) easily gets AC in 0.078s. |
|
|
