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

2017-02-06 00:21:44 Tabris_ 阅读数：587

博客爬取于2020-06-14 22:41:52
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54885329

题目连接:http://codeforces.com/problemset/problem/763/B

-------------------------------------------------------------------------------------------.
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

-------------------------------------------------------------------------------------------.
题目大意:
就是在一个二维平面上有n个矩形,现在让你给这n个矩形4种涂色之一,使得相邻的矩形颜色不同.
(矩形的两条边都是整数)
解题思路:

我这种智障是做不出来的,本来并不想写题解,但是无意中看了Tutorial中的discuss发现一个特别容易理解的.

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.
我们可能会认为我们的矩形被画在无限平方的纸。将纸分成一个个2×2方块,然后从左上角顺时针方向开始标上1,2,3,4(代表颜色)。由于每个矩形的两边都是奇数长度，所以它的所有格子标记为相同的数。让我们用1，2，3，4个不同的颜色编号，并绘制每个矩形的颜色的数字标记的格子。很容易看出，任何两个相邻矩形的角的数是不同的。
(基本是机翻…可以自己画一画就容易理解了,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;
}