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.
The first line contains singe integer N.
Each of next N lines contains two integers Xi and Yi denotine the coordinates of i-th point.
In a single line print single integer - the minimal number of points Chef need to paint to receive at least one square.
- 0 ≤ N ≤ 2000
- -10^6 ≤ Xi, Yi ≤ 10^6
- There are NO coincided points
Input: 3 0 0 2 2 3 3 Output: 2 Input: 5 0 0 100 100 200 200 100 0 0 100 Output: 0
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).
|Tags||berezin easy geometry oct14|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.