3718: [PA2014]Parking
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 125 Solved: 65
[Submit][Status][Discuss]
Description
你的老板命令你将停车场里的车移动成他想要的样子。
停车场是一个长条矩形，宽度为w。我们以其左下角顶点为原点，坐标轴平行于矩形的边，建立直角坐标系。停车场很长，我们可以认为它一直向右边伸展到无穷远处。
车都是边平行于坐标轴的矩形，大小可能不同。你可以将车任意地平移（但不能旋转），只要他们不超出停车场的边界，且不能互相碰撞，但紧挨着是允许的（即任意时刻任两辆车的重叠面积为0）。
你知道目前各辆车的摆放位置，以及老板心中所想的位置。你需要判断是否可以办到老板的任务。
Input
第一行为一个整数t(1<=t<=20)，表示测试数据数量。
对于每组测试数据，第一行两个整数n,w(1<=n<=50000,1<=w<=10^9)，分别表示车的数量和停车场的宽度。
接下来n行，第i行有四个整数x1,y1,x2,y2(0<=x1,x2<=10^9,0<=y1,y2<=w)，表示编号为i的车的当前位置是由x1,y1,x2,y2确定的矩形。（注意：数据有可能出现x1>x2或y1>y2）
再接下来n行，格式和意义同上，表示车的目标位置。
Output
输出t行，第i行为TAK（是）或NIE（否），表示第i组测试数据中能否按照要求进行移动。
Sample Input
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
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
Sample Output
TAK
NIE
NIE
HINT
Source
两辆车可以互相穿过的条件是两辆车的宽度加起来不超过m。。然后依次移动车判断是否不符即可。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
struct data{int x1,x2,y1,y2,w,id;} s1[N],s2[N];
int s[N],pos[N],n,m,T,F;
bool operator < (data a,data b){
if (a.x1==b.x1) return a.x2<b.x2;
return a.x1<b.x1;
}
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
int lowbit(int x){return x&-x;}
int Query(int pos){
int res = 0;
for (int i=pos;i;i-=lowbit(i)) res = max(res,s[i]);
return res;
}
void Insert(int pos,int val){for (int i=pos;i<=n;i+=lowbit(i)) s[i] = max(s[i],val);}
int main(){
T = read();
while (T--){
memset(s,0,sizeof(s));memset(pos,0,sizeof(pos));
n = read();m = read();
for (int i=1;i<=n;i++){
s1[i].x1 = read();s1[i].y1 = read();
s1[i].x2 = read();s1[i].y2 = read();
if (s1[i].x2<s1[i].x1) swap(s1[i].x1,s1[i].x2);
if (s1[i].y2<s1[i].y1) swap(s1[i].y1,s1[i].y2);
s1[i].w = s1[i].y2-s1[i].y1;s1[i].id = i;
}
for (int i=1;i<=n;i++){
s2[i].x1 = read();s2[i].y1 = read();
s2[i].x2 = read();s2[i].y2 = read();
if (s2[i].x2<s2[i].x1) swap(s2[i].x1,s2[i].x2);
if (s2[i].y2<s2[i].y1) swap(s2[i].y1,s2[i].y2);
s2[i].w = s2[i].y2-s2[i].y1;s2[i].id = i;
}
sort(s1+1,s1+1+n);sort(s2+1,s2+1+n);
for (int i=1;i<=n;i++) pos[s1[i].id] = i;
F = 1;
for (int i=n;i && F;i--){
if (Query(pos[s2[i].id])+s2[i].w>m) {F = 0;break;}
Insert(pos[s2[i].id],s2[i].w);
}
if (F) printf("TAK\n");
else printf("NIE\n");
}
}
评论 (0)
