2067 - City Houses

Created by Ray Williams Robinson Valiente
Added by ymondelo20 (2012-10-12)
Limits
Total Time: 30000 MS | Test Time: 6000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

Squared City is a town from a country very far away. As its name suggests, people there love squared shapes, so the whole city can be seen as a huge grid where all houses are located at corners. This year the International House Neighboring Contest will be held there, and everyone in town will take part on it. To win the competition, a person should answer, as fast as possible, what is the minimum distance between his house and any other house. Judges have faced troubles over the years to determine the correctness of the answers. This is where you get in. You need to compute, for each house, the minimum distance to any of the other houses and report them. As the contest will be held at Square City, the distance between houses at (x1, y1) and (x2, y2) is the number of blocks you need to walk from one to the other, or in other words |x1 – x2| + |y1 – y2|.
Squared City is a town from a country very far away. As its name suggests, people there love squared shapes, so the whole city can be seen as a huge grid where all houses are located at corners. This year the International House Neighboring Contest will be held there, and everyone in town will take part on it. To win the competition, a person should answer, as fast as possible, what is the minimum distance between his house and any other house. Judges have faced troubles over the years to determine the correctness of the answers. This is where you get in. You need to compute, for each house, the minimum distance to any of the other houses and report them. As the contest will be held at Square City, the distance between houses at (x1, y1) and (x2, y2) is the number of blocks you need to walk from one to the other, or in other words |x1 – x2| + |y1 – y2|.
Squared City is a town from a country very far away. As its name suggests, people there love squared shapes, so the whole city can be seen as a huge grid where all houses are located at corners. This year the International House Neighboring Contest will be held there, and everyone in town will take part on it. To win the competition, a person should answer, as fast as possible, what is the minimum distance between his house and any other house. Judges have faced troubles over the years to determine the correctness of the answers. This is where you get in. You need to compute, for each house, the minimum distance to any of the other houses and report them. As the contest will be held at Square City, the distance between houses at (x1, y1) and (x2, y2) is the number of blocks you need to walk from one to the other, or in other words |x1 – x2| + |y1 – y2|.

Input specification

Input begins with a single integer N (1 < N <= 10^5) denoting how many houses there are in town. N lines follow, each one containing two non-negative integers x, y (x, y <= 10^7) saying the location of a single house. No two houses are located at the same place.
Input begins with a single integer N (1 < N <= 10^5) denoting how many houses there are in town. N lines follow, each one containing two non-negative integers x, y (x, y <= 10^7) saying the location of a single house. No two houses are located at the same place.
Input begins with a single integer N (1 < N <= 10^5) denoting how many houses there are in town. N lines follow, each one containing two non-negative integers x, y (x, y <= 10^7) saying the location of a single house. No two houses are located at the same place.

Output specification

Your output should consist of exactly N lines. The i-th line should contain the answer for the i-th house according to the input order.
Your output should consist of exactly N lines. The i-th line should contain the answer for the i-th house according to the input order.
Input begins with a single integer N (1 < N <= 10^5) denoting how many houses there are in town. N lines follow, each one containing two non-negative integers x, y (x, y <= 10^7) saying the location of a single house. No two houses are located at the same place.

Sample input

5
0 0
1 1
2 2
3 3
4 4

Sample output

2
2
2
2
2

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/