<原># codeforces 763B. Timofey and rectangles [思维]【智商】

# codeforces 763B. Timofey and rectangles [思维]【智商】

2017年02月06日 00:21:44 Tabris_ 阅读数：563

https://blog.csdn.net/qq_33184171/article/details/54885329

——————————————————————————————-.
time limit per test2 seconds
memory limit per test256 megabytes

inputstandard input
outputstandard output

One of Timofey’s birthday presents is a colourbook in a shape of an infinite
plane. On the plane n rectangles with sides parallel to coordinate axes are
situated. All sides of the rectangles have odd length. Rectangles cannot
intersect, but they can touch each other.

Help Timofey to color his rectangles in 4 different colors in such a way that
every two rectangles touching each other by side would have different color,
or determine that it is impossible.

Two rectangles intersect if their intersection has positive area. Two
rectangles touch by sides if there is a pair of sides such that their
intersection has non-zero length

The picture corresponds to the first example
Input
The first line contains single integer n (1 ≤ n ≤ 5·105) — the number of
rectangles.

n lines follow. The i-th of these lines contains four integers x1, y1, x2 and
y2 ( - 109 ≤ x1 < x2 ≤ 109,  - 109 ≤ y1 < y2 ≤ 109), that means that points
(x1, y1) and (x2, y2) are the coordinates of two opposite corners of the i-th
rectangle.

It is guaranteed, that all sides of the rectangles have odd lengths and
rectangles don’t intersect each other.

Output
Print “NO” in the only line if it is impossible to color the rectangles in 4
different colors in such a way that every two rectangles touching each other
by side would have different color.

Otherwise, print “YES” in the first line. Then print n lines, in the i-th of
them print single integer ci (1 ≤ ci ≤ 4) — the color of i-th rectangle.

Example

input

8
0 0 5 3
2 -1 5 0
-3 -4 2 -1
-1 -1 2 0
-3 0 0 5
5 2 10 3
7 -3 10 2
4 -2 7 -1

output

YES
1
2
2
3
2
2
4
1

——————————————————————————————-.

(矩形的两条边都是整数)

We may assume that our rectangles are drawn on an infinite sheet of squared
paper. Divide it into squares 2 × 2 and mark the cells in each square by 1, 2,
3, 4 clockwise starting from the upper left corner. Since both sides of each
rectangle are of odd length, its corner cells are marked by the same number.
Let us number four different colors by 1, 2, 3, 4 and paint each rectangle
with the color whose number marks the corner cells. It is readily seen that
the numbers in the corners of any two adjacent rectangles are distinct.

(基本是机翻……可以自己画一画就容易理解了,Orz)

——————————————————————————————-.

``````int main(){
int x1,x2,y1,y2;
int n ;
s1(n);puts("YES");
Rep(i,1,n){
s1(x1),s1(x2),s1(y1),s1(y2);
x1=(x1%2+2)%2;
x2=(x2%2+2)%2;
printf("%d\n",x1+x2*2+1);
}
return 0;
}
``````

上一篇 <原># The 10th Zhejiang Provincial Collegiate Programming Contest

2017-02-06 <原># 浪费生命啊

2017-02-02
目录