OCC '19 G4 - Willson and Fighting

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Willson the Canada Goose is like any other Canada Goose - he can sometimes become upset with other geese (or humans) and begin to fight them. However, geese will never fight with their mates.

After migrating back from California, Willson's extended family, consisting of 2N geese, are grazing in a field. The i^{th} goose is located at (x_i,y_i), and no two geese will share the same location. Define the distance between the p^{th} goose and the q^{th} goose to be \text{dist}(p,q) = |x_p-x_q|+|y_p-y_q|, that is, the Manhattan distance.

For 1 \le k \le N, the (2k-1)^{th} and (2k)^{th} geese are mates. Suppose two geese p and q are mates. Then for any other goose r, goose p will honk at goose r if \text{dist}(p,r) < \text{dist}(p,q). Similarly, goose q will honk at goose r if \text{dist}(q,r) < \text{dist}(p,q).

If two geese honk at each other, then they will fight once. Can you determine the number of fights that each goose will get into?

Input Specification

The first line of input will contain N.

2N lines of input follow. The i^{th} line will contain integers x_i, y_i.

Output Specification

Output 2N lines. On the i^{th} line, output the number of fights that goose i will get into.

Sample Input

1 1
3 1
4 1
6 1
1 21
1 23
1 24
1 25

Sample Output


Explanation for Sample Output

Goose 2 and goose 3 will honk at each other, so they fight. Note that goose 7 does not honk at goose 6, so these two geese do not fight.


1 \le N \le 60\,000 and all coordinates c satisfy 1 \le c \le 60\,000. No two geese will share the same location.

Subtask Points Additional constraints
1 15 N \le 2\,000
2 45 1 \le c \le 1\,000
3 40 No additional constraints.


There are no comments at the moment.