A22601.Parking
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
你的老板命令你将停车场里的车移动成他想要的样子。
停车场是一个长条矩形,宽度为 w。我们以其左下角顶点为原点,坐标轴平行于矩形的边,建立直角坐标系。停车场很长,我们可以认为它一直向右边伸展到无穷远处。
车都是边平行于坐标轴的矩形,大小可能不同。你可以将车任意地平移(但不能旋转),只要他们不超出停车场的边界,且不能互相碰撞,但紧挨着是允许的(即任意时刻任两辆车的重叠面积为 0)。
你知道目前各辆车的摆放位置,以及老板心中所想的位置。你需要判断是否可以办到老板的任务。
输入格式
第一行为一个整数 t,表示测试数据数量。
对于每组测试数据,第一行两个整数 n,w,分别表示车的数量和停车场的宽度。
接下来 n 行,第 i 行有四个整数 x1,y1,x2,y2,表示编号为 i 的车的当前位置是由 x1,y1,x2,y2 确定的矩形。
(注意:数据有可能出现 x1>x2 或 y1>y2)
再接下来 n 行,格式和意义同上,表示车的目标位置。
输出格式
输出 t 行,第 i 行为 TAK
(是)或 NIE
(否),表示第 i 组测试数据中能否按照要求进行移动。
输入输出样例
输入#1
2 3 3 0 0 2 2 2 1 4 3 4 0 6 1 0 0 2 2 2 1 4 3 0 2 2 3 3 3 0 0 2 2 2 1 4 3 4 0 6 1 2 1 4 3 0 0 2 2 4 0 6 1
输出#1
TAK NIE
说明/提示
对于 100% 的数据,1≤t≤20,1≤n≤5×104,1≤w≤109,0≤x1,x2≤109,0≤y1,y2≤w。