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

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

2017年02月06日 00:21:44 Tabris_ 阅读数:563
标签: codeforces

个人分类: codeforces 思维


博客爬取于2019-04-18 17:18:02
以下为正文

版权声明:本文为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;
}

 上一篇
<原>#  The 10th Zhejiang Provincial Collegiate Programming Contest <原># The 10th Zhejiang Provincial Collegiate Programming Contest
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-02-06
下一篇 
<原>#  浪费生命啊 <原># 浪费生命啊
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-02-02
  目录