问题描述
想要找出经过gaowei区域的居民,分析位置记录是一种简单有效的方法。
具体来说,一位居民的位置记录包含t个平面坐标(x1,y1),(x2,y2),…,(xt,yt) ,其中(xi,yi)表示该居民i时刻所在位置。
gaowei区域则可以抽象为一个矩形区域(含边界),左下角和右上角的坐标分别为(xl,yd)和(xr,yu),满足xl<xr且yd<yu。
考虑某位居民的位置记录,如果其中某个坐标位于矩形内(含边界),则说明该居民经过gaowei区域;进一步地,如果其中连续
k个或更多坐标均位于矩形内(含边界),则认为该居民曾在gaowei区域逗留。需要注意的是,判定经过和逗留时我们只关心位置记录中的t个坐标,而无需考虑该居民在i到i+1时刻之间位于何处。
给定gaowei区域的范围和n位居民过去t个时刻的位置记录,试统计其中经过gaowei区域的人数和曾在gaowei区域逗留的人数。
输入格式
输入共n+1行。
第一行包含用空格分隔的七个整数n、k、t、xl、yd、xr和yu,含义如上文所述。
接下来n行,每行包含用空格分隔的2t个整数,按顺序表示一位居民过去t个时刻的位置记录(x1,y1),(x2,y2),…,(xt,yt) 。
输出格式
输出共两行,每行一个整数,分别表示经过高危区域的人数和曾在高危区域逗留的人数。
样例输入1
5 2 6 20 40 100 80
100 80 100 80 100 80 100 80 100 80 100 80
60 50 60 46 60 42 60 38 60 34 60 30
10 60 14 62 18 66 22 74 26 86 30 100
90 31 94 35 98 39 102 43 106 47 110 51
0 20 4 20 8 20 12 20 16 20 20 20
样例输出1
3
2
正确的代码(for循环):
#include<iostream>
using namespace std;
int xl,yd,xr,yu;
bool check(int x,int y){//判断是否在矩形内
if(x>=xl && x<=xr && y>=yd && y<=yu){
return true;
}
return false;
}
int main(){
int n,k,t;
cin>>n>>k>>t>>xl>>yd>>xr>>yu;
int x,y;
int through=0;//经过高危区域的人数
int stay=0;//曾在高危区域逗留的人数
int res;
for(int i = 1; i <= n; i++){//问题:这里改成 while(n--) 就会超时?
int cnt=0;
bool flag1=false,flag2=false;//记录此人是 经过flag1/逗留flag2
for(int j = 1; j <= t; j++) {
cin>>x>>y;
if(check(x,y)){
cnt++;
flag1=true;//经过
}
else cnt=0;
if(cnt==k)flag2=true;//逗留
}
if(flag1)through++;
if(flag2)stay++;
}
cout<<through<<endl;
cout<<stay<<endl;
return 0;
}
改成while:
#include<iostream>
using namespace std;
int xl,yd,xr,yu;
bool check(int x,int y){//判断是否在矩形内
if(x>=xl && x<=xr && y>=yd && y<=yu){
return true;
}
return false;
}
int main(){
int n,k,t;
cin>>n>>k>>t>>xl>>yd>>xr>>yu;
int x,y;
int through=0;//经过高危区域的人数
int stay=0;//曾在高危区域逗留的人数
int res;
while(n--){//改!!!!!!!!!!!!!
int cnt=0;
bool flag1=false,flag2=false;//记录此人是 经过flag1/逗留flag2
while(t--){//改!!!!!!!!!!!!!
cin>>x>>y;
if(check(x,y)){
cnt++;
flag1=true;//经过
}
else cnt=0;
if(cnt==k)flag2=true;//逗留
}
if(flag1)through++;
if(flag2)stay++;
}
cout<<through<<endl;
cout<<stay<<endl;
return 0;
}
改完后就运行样例一就超时了,这是为什么呀