Problem 1206 - USTC Online Judge

Rank

Problem 1206

切蛋糕

Time Limit: 2000ms
Memory Limit: 65536kb

Description

KK是个心灵手巧的好姑娘，她做了一个大蛋糕请她的好朋友们来品尝。
这个蛋糕分成n×n个正方形小格，每个小格包含一块水果。KK要把蛋糕切成若干块，显然她不会破坏任意一个小格。
无聊的某同学在她切蛋糕时不停地问她同一种问题：某两个小格是否还在同一块蛋糕里？
例如下图中，KK从(1,1)切到(4,1)，又从(1,1)切到(1,4)，从而将蛋糕分成了两块。然后又从(2,1)切到(2,3)，从(1,3)切到(2,3)，于是把整个蛋糕分成了三块。其中小格(2,2)只和小格(2,3)连通，与其它所有小格不连通。

KK被这些无聊的问题烦透了，她请求你编写一个程序让他闭嘴。

Input

输入包括多组数据。
每组数据第一行为两个整数：蛋糕大小n (1≤n≤1000)，以及KK切蛋糕次数和问题数之和q (1≤q≤100000)
然后q行，每行是下面两者之一，描述了切蛋糕和问问题的过程：

cut x1 y1 x2 y2
沿着坐标(x1,y1)和(x2,y2)连成的直线段切割蛋糕。
输入数据确保x1=x2和y1=y2恰有其一成立，坐标(x1,y1)和(x2,y2)连成的直线段一定在蛋糕内部，并且KK不会重复切同一位置。
query x1 y1 x2 y2
询问格子(x1,y1)和(x2,y2)是否在同一块蛋糕上(1≤x1, y1, x2, y2≤n)

输入数据以n=q=0结束。

Output

对于输入数据中的query问题，如果两个格子在同一块蛋糕上则输出”Yes”，否则输出”No”。

Sample Input

4 11
query 1 1 2 2
cut 1 1 4 1
cut 1 1 1 4
query 1 1 2 2
query 2 2 3 3
cut 2 3 2 1
query 2 2 3 3
cut 1 3 2 3
query 2 2 3 3
query 2 2 2 3
query 1 1 2 4
1000 1
query 1 1 1000 1000
0 0

Sample Output

Yes
No
Yes
Yes
No
Yes
No
Yes

[Submit|Status|Discuss|Add to bookmark]