Status:  Past  Start:  20121013 12:15:00  End:  20121013 16:15:00 
The 2012 Caribbean National Contests of the ACMICPC (CUB)
Problem
2067  City Houses
Created by  Ray Williams Robinson Valiente 
Added by  ymondelo20 (20121012) 
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 nonnegative 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 nonnegative 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 nonnegative 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 ith line should contain the answer for the ith house according to the input order.
Your output should consist of exactly N lines. The ith line should contain the answer for the ith 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 nonnegative 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/