Problem description
Topic background
After the outbreak of an epidemic in a certain place, we want to inform all residents who have recently passed through the high-risk area to participate in nucleic acid testing in accordance with the principle of "testing as much as possible".
Problem description
In order to find out the residents passing through high-risk areas, analyzing location records is a simple and effective method.
Specifically, a resident's location record contains
t
t
t plane coordinates
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
⋯
,
(
x
t
,
y
t
)
(x1,y1),(x2,y2),⋯,(xt,yt)
(x1,y1),(x2,y2), (xt,yt), where
(
x
i
,
y
i
)
(xi,yi)
(xi,yi) indicates the location of the resident i at all times.
The high-risk area can be abstracted as a rectangular area (including boundary), and the coordinates of the lower left corner and the upper right corner are
(
x
l
,
y
d
)
(xl,yd)
(xl,yd) and
(
x
r
,
y
u
)
(xr,yu)
(xr,yu), satisfied
x
l
<
x
r
xl<xr
XL < XR and
y
d
<
y
u
yd<yu
yd<yu.
Consider the location record of a resident. If one of the coordinates is in a rectangle (including boundary), it means that the resident passes through the high-risk area; Further, if one of them is continuous k k If k or more coordinates are located in the rectangle (including the boundary), the resident is considered to have stayed in the high-risk area. It should be noted that when determining passing and staying, we only care about the information in the location record t t t coordinates, regardless of where the resident is i i i to i + 1 i+1 Where is i+1 time.
Scope and of a given high-risk area n n n residents in the past t t Record the location at t times, and try to count the number of people passing through the high-risk area and the number of people who have stayed in the high-risk area.
Input format
Enter a total of n+1 lines.
The first line contains seven integers n, k, t, xl, yd, xr, and yu separated by spaces, meaning as described above.
The next n lines contain 2t integers separated by spaces, which represent the location records of a resident in the past t times in order ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x t , y t ) (x1,y1),(x2,y2),⋯,(xt,yt) (x1,y1),(x2,y2),⋯,(xt,yt).
Output format
The output consists of two lines, with an integer in each line, representing the number of people passing through the high-risk area and the number of people who have stayed in the high-risk area.
Sample input 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
Sample output 1
3 2
Example 1 Description
As shown by the red mark in the figure below, the first three position records pass through the high-risk area;
However, the third position record (the upper left curve in the figure) is located in the high-risk area at only one time and does not meet the conditions of stay.
Sample input 2
1 3 8 0 0 10 10 -1 -1 0 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0
Sample output 2
1 0
Example 2 Description
The location records that it has passed through the high-risk area, but it is located in it for at most two consecutive times, which does not meet the conditions of stay.
Scale and agreement of evaluation cases
All test points meet 1 ≤ n ≤ 20 1≤n≤20 1≤n≤20， 1 ≤ k ≤ t ≤ 1 0 3 1≤k≤t≤10^3 1 ≤ k ≤ t ≤ 103, all coordinates are integers and the absolute value does not exceed 1 0 6 10^6 106.
problem analysis
Several important conditions in the question:
- There are n residents in total, and each resident has n location coordinates;
- For each position coordinate (x, y), meet x l < = x < = x r xl<=x<=xr XL < = x < = XR and y d < = y < = y u yd<=y<=yu When YD < = y < = Yu, the point is in the high-risk area;
- For each resident, if there is a location coordinate in the high-risk area, it is passing through the high-risk area; If there are at least k consecutive position coordinates in the high-risk area, it means staying in the high-risk area.
The final requirement is: the number of people passing through and staying in high-risk areas among n residents
Therefore, it is not difficult to find out that we need to determine whether each point exists in the high-risk area, and then count the maximum number of coordinates of each resident in the high-risk area, so as to obtain whether the resident stays in the high-risk area.
Full decomposition method
For each position coordinate, we can define a structure to represent, including horizontal and vertical coordinates, and then use a variable flag to mark whether the point is in the high-risk area.
For all position coordinates, we define a two-dimensional array records to store, r e c o r d s [ i ] [ j ] records[i][j] records[i][j] represents the jth location of the ith resident. Note that the size and space of the array must be allocated enough space according to the maximum value in the question, otherwise it will run incorrectly.
typedef struct point{
int x, y; //coordinate
int flag; //Mark whether the point is in the high-order area, and the value is 1 in the area
}point;
point records[30][1010];
We only need to traverse the two-dimensional array to determine the location coordinates of each resident r e c o r d s [ i ] [ 0 ] records[i][0] records[i][0] to r e c o r d s [ i ] [ t − 1 ] records[i][t-1] records[i][t − 1], maxNum represents the maximum number of points continuously in the high-risk area. A count variable count is used to count the number of points continuously in the high-risk area during the traversal process. When flag = 1, add 1, when 0, update the maximum value, and set count to 0.
for(int i=0; i<n; i++) {
int count = 0;
int maxNum = 0; //The maximum continuous stay time of the resident in the high-risk area
for(int j=0; j<t; j++) {
if(records[i][j].flag == 1) count++;
else {
maxNum = max(maxNum, count);
count = 0;
}
}
maxNum = max(maxNum, count);
}
Finally, the complete code is as follows:
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
typedef struct point{
int x, y; //coordinate
int flag; //Mark whether the point is in the high-order area, and the value is 1 in the area
}point;
point records[30][1010];
int main() {
int n, k, t, xl, yd, xr, yu;
cin >> n >> k >> t >> xl >> yd >> xr >> yu;
for(int i=0; i<n; i++) {
for(int j=0; j<t; j++) {
cin >> records[i][j].x >> records[i][j].y;
//Judge whether the point is in the high-risk area
if(records[i][j].x >= xl && records[i][j].x <= xr && records[i][j].y >= yd && records[i][j].y <= yu) {
records[i][j].flag = 1;
}else records[i][j].flag = 0;
}
}
int pNum = 0; //Number of people passing through high-risk areas
int lNum = 0; //Number of people staying in high-risk areas
for(int i=0; i<n; i++) {
int count = 0;
int maxNum = 0; //The maximum continuous stay time of the resident in the high-risk area
for(int j=0; j<t; j++) {
if(records[i][j].flag == 1) count++;
else {
maxNum = max(maxNum, count);
count = 0;
}
}
maxNum = max(maxNum, count);
if(maxNum > 0) pNum++;
if(maxNum >= k) lNum++;
}
cout << pNum <<endl;
cout << lNum <<endl;
return 0;
}
