CHASE - A Chase In WonderLand
Alice is in Wonderland. It is March and March Hare is raving mad. It begins to chase Alice. Alice runs as fast as she can, but she comes to the the edge of a quicksand pool. Now this pool has several safe spots where she may comfortably step on without being swallowed by the quicksand. She may step onto any safe spot from solid ground, but thereafter she can jump from spot to spot only in a straight line, and she cant turn back. March Hare is still hot on her heels, so she needs to know the maximum number of jumps she can make.
On the first line there will be a single integer n, denoting the number of test cases. Each test case will consist of a single integer k by itself on a line, followed by k lines containing the x and y co-ordinates of the safe spots , seperated by a single space. Both coordinates are integer values. There are no leading or trailing spaces or blank lines. 0<k≤2200
For each case print a single integer by itself on a line, with no leading or trailing spaces. Do not print blank lines.
Input: 2 5 0 0 1 1 2 2 4 8 2 75 3 0 0 1 2 3 4 Output: 2 1
TLE on O(K^2 logK)
A very strict time limit. Consider increasing it to 2s.
please keep time limit to such extend that TLE should not be there because of IO. I got accepted after IO optimization. O(n^2) solutionLast edit: 2011-02-04 14:21:25
I got TLE with a an O(K^2 log K) solution too T_T
Miguel already solved this one, but for other people with this problem: It is possible, but you will have to use fast structures like arrays (if you know the O(K^2 log K) algo you should know what I'm reffering to).
I keep getting TLE with a an O(K^2 log K) solution, could anyone point me an efficient algoritm?