## STC05 - Garden

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 <= 10^{5}, 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 X_{i} and Y_{i}, -10^{6} <= X_{i}, Y_{i }<= 10^{6}, 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 |