Chef and Square

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves squares! You are given N points with integers coordinates, Chef asks you to find out how many points he should add to these set of N points, so that one could create at least one square having its vertices from the points of the resulting set. Note that the square created need not to be parallel to the axis.
Input
The first line contains singe integer N.
Each of next N lines contains two integers X_{i} and Y_{i} denotine the coordinates of ith point.
Output
In a single line print single integer  the minimal number of points Chef need to paint to receive at least one square.
Constraints
 0 ≤ N ≤ 2000
 10^6 ≤ X_{i}, Y_{i} ≤ 10^6
 There are NO coincided points
Example
Input: 3 0 0 2 2 3 3 Output: 2 Input: 5 0 0 100 100 200 200 100 0 0 100 Output: 0
Explanation
For the first example Chef can add points (2, 0), (0, 2) or (2, 3), (3, 2)
For the second example Chef already has square (0, 0), (100, 0), (0, 100), (100, 100).
Author:  berezin 
Tester:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/CHEFSQUA 
Tags  berezin, easy, geometry, oct14 
Date Added:  3042014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions