STC05 - Garden

no tags 

Byteen, Byteasar's wife, simply loves flowers. She has decided to have a garden near their house. Byteen is a perfectionist: she would like her garden to be square with sides parallel to North-South and East-West directions. Moreover, Byteen wants each corner of the garden to contain one of the N apple-trees growing nearby.

Byteasar has learned about his wife's plans just before the final match of the World Cup in soccer. He knows that his wife is keen about the garden and, therefore, that it must be created instantly. To save some time, he asked her what exactly is her dream location of the garden - he knows that Byteen will surely check all the possibilities before making a final decision. Help Byteasar to find out how much time he has left, assuming that checking a single location for the garden takes Byteen exactly one second.

Input

The first line of the input contains one integer N, 1 <= N <= 105, the number of apple-trees growing near Byteen's and Byteasar's house. For simplicity, the locations of trees are given in a Cartesian coordinate system. Each of the following N lines contains two space-separated integers Xi and Yi, -106 <= Xi, Yi <= 106, the coordinates of the i-th apple-tree. No pair of coordinates appears in the input twice.

Output

Your program should print a single integer: the number of seconds Byteen will spend on checking all possible locations of the garden, each location containing apple-trees in all its corners.

Example

For the input data:

6
0 0
0 1
1 0
1 1
3 0
3 1

the correct result is:

1

hide comments
Luis: 2013-09-21 16:52:16

It would be nice to know, despite time limit and within some reasonable tolerance, if the result is correct or not.


Added by:Tooru Ichii
Date:2013-08-06
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:ONTAK 2010