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.
Input
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 coordinates 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
Output
For each case print a single integer by itself on a line, with no leading or trailing spaces. Do not print blank lines.
Example
Input: 2 5 0 0 1 1 2 2 4 8 2 75 3 0 0 1 2 3 4 Output: 2 1
hide comments
sherlock11:
20180202 04:49:35
nice problem..................


kass_97:
20170114 11:13:30
No IO optimization needed, O(n^2) works fine, killed it in 0.13 sec in first attempt :D 

Vipul Srivastava:
20160206 18:21:31
O(k^2) with unordered_map giving TLE.. 

Yogendra Kumar:
20151209 11:19:03
OMG! O(K^2) is giving TLE in java. I believe this problem is not for java.


Dushyant Singh:
20150912 10:41:50
What is the range of coordinates? Is it exactly same as range of int? 

Jaswanth:
20150822 14:33:06
use double do not use float 

:(:
20150424 17:12:30
O( N^2 (logN) ) does work... :) 

Venkatesh Ganesan:
20140206 14:00:20
very strict time limit. can increase it a bit. 

Saurabh Jain:
20130705 12:57:33
AC at one go :) No need to go for IO optimization. scanf() and printf() in C/C++ will suffice to get AC with a good algo. 

uberness132:
20121112 23:32:56
TLE on O(K^2 logK) 
Added by:  Abhilash I 
Date:  20070222 
Time limit:  0.192s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Code Craft 2007 