UFO Landing

Egypt's largest city, Heliozen is famous for its UFO landing pad. Every now and then people see some UFO landing at the landing pad.Each UFO is circular in shape and lands on 4 pedestals, each of which touches the ground on a point. The pedestals are located at the corner of a square at the base of the UFO. Whenever any UFO touches the ground they leave some radioactive material on the ground at their landing points. The scientists at Heliozen return after a long break and analyze the concentrations of radioactivity at all points and take a note of the points which show traces of radioactive concentrations highlighting the landing of UFO at those points. The scientists may by mistake spot some erroneous points as well.Given a set of integer points where scientists observed radioactivity, help the scientists find the maximum number of UFOs that landed at the landing pad given that no two UFOs land exactly at all four same pedestal points and that no two UFO land at the same time.
Input
The first line of input is an integer N, denoting the number of radioactive points spotted by the scientists. This is followed by N lines of input describing the points. Each of these lines consist of two integers X and Y, the x and y coordinate of the point.
Output
A single integer, denoting the maximum number of UFOs that landed on the landing pad(given that no two UFOs have all four landing points same)
Constraints
The maximum number of radioactive points spotted by scientist is less than 2000 and less than 500 in 30% of the cases.
The coordinates of the N points can be arbitrary integers(will fit in an int).
Input: 11 6 3 0 3 2 3 6 5 0 5 2 5 4 1 2 7 3 4 6 7 7 5 Output: 3
Author:  rahulsingal14 
Tags  rahulsingal14 
Date Added:  26022011 
Time Limit:  1.94444 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions