P7865 「EVOI-RD1」无人机航拍
题目背景
T 市举行活动需要拍摄高空俯瞰图，找来了一个无人机机队负责拍摄工作。 一E孤行 是队伍的队长，他根据广场的规模来安排无人机的位置。
题目描述
有一个广场，可以看做是一个n × m n \times mn×m的矩形；一E孤行 一共有s ss架无人机，每架无人机的拍摄范围也可以看做是一个矩形，无人机机队的拍摄范围为所有无人机拍摄范围的并。
一E孤行 负责安排无人机的位置，而总负责人 WuuTue 要验收她他的方案。WuuTue 的验收方法是列举出L LL个重要的区域，每个重要区域也是一个矩形。 一E孤行 方案的优秀程度取决于有多少个重要区域完全在无人机机队的拍摄范围中。
因此，对于每一个重要区域， 一E孤行 想知道它是否完全在无人机机队的拍摄范围中。
输入格式
第一行，用空格隔开的两个整数n nn和m mm，用来描述广场的大小。
第二行，一个整数s ss，表示无人机队伍中无人机的总数量。
第三行到第s + 2 s+2s+2行，每行四个用空格隔开的整数，a 1 , b 1 , a 2 , b 2 a_1,b_1,a_2,b_2a1,b1,a2,b2，用来描述一架无人机的拍摄范围。其中a 1 , b 1 a_1,b_1a1,b1表示矩形的左下角坐标，a 2 , b 2 a_2,b_2a2,b2表示右上角的坐标。
第s + 3 s+3s+3行，一个整数L LL，表示活动总负责人列出的重要区域的数量L LL。
最后L LL行，每行四个用空格隔开的整数r 1 , c 1 , r 2 , c 2 r_1,c_1,r_2,c_2r1,c1,r2,c2，用来描述一个重要区域。其中r 1 , c 1 r_1,c_1r1,c1表示矩形区域左下角坐标，r 2 , c 2 r_2,c_2r2,c2表示右上角坐标。
输出格式
输出L LL行，对于每个重要区域，如果完全在机队的拍摄范围内就输出Yes，否则出No。每个答案占一行。
输入输出样例 #1
输入 #1
9 9 3 2 1 4 4 2 5 4 9 5 2 7 6 2 3 3 6 6 5 6 8 8输出 #1
Yes No说明/提示
样例说明
如下图所示，区域A , B , C A,B,CA,B,C分别是某某安排的无人机能够覆盖的范围，区域D , E D,ED,E是 WuuTue 要验收时列举的重点区域，区域D DD能够被完全覆盖，区域E EE不能被全部覆盖。
数据规模与约定
本题采用捆绑测试。
对于40 % 40\%40%的数据：1 ≤ n ≤ 1000 1 \le n \le 10001≤n≤1000，1 ≤ s ≤ 100 1 \le s \le 1001≤s≤100。
对于100 % 100\%100%的数据：
- 1 ≤ n , m ≤ 3 × 10 3 1 \le n, m \le 3 \times 10^{3}1≤n,m≤3×103。
- 1 ≤ s , L ≤ 10 6 1 \le s,L \le 10^61≤s,L≤106。
- 1 ≤ x 1 < x 2 ≤ n 1 \le x_1 < x_2 \le n1≤x1<x2≤n。
- 1 ≤ r 1 < r 2 ≤ n 1 \le r_1 < r_2 \le n1≤r1<r2≤n。
- 1 ≤ y 1 < y 2 ≤ m 1 \le y_1 < y_2 \le m1≤y1<y2≤m。
- 1 ≤ c 1 < c 2 ≤ m 1 \le c_1 < c_2 \le m1≤c1<c2≤m。
C++实现
#include<iostream>#include<algorithm>#defineMAXN3005#defineMAXM3005#defineMAXS1000005usingnamespacestd;intn,m,s,l;intsqu[MAXN][MAXM];// 使用一个矩阵即可intmain(){std::ios::sync_with_stdio(false);cin>>n>>m>>s;for(inti=1;i<=s;i++){inta1,b1,a2,b2;cin>>a1>>b1>>a2>>b2;squ[a1][b1]++;squ[a2+1][b2+1]++;squ[a2+1][b1]--;squ[a1][b2+1]--;}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){squ[i][j]+=squ[i-1][j]+squ[i][j-1]-squ[i-1][j-1];}}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(squ[i][j])squ[i][j]=1;}}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){squ[i][j]+=squ[i-1][j]+squ[i][j-1]-squ[i-1][j-1];}}cin>>l;for(inti=1;i<=l;i++){intr1,c1,r2,c2;cin>>r1>>c1>>r2>>c2;intsum=squ[r2][c2]-squ[r1-1][c2]-squ[r2][c1-1]+squ[r1-1][c1-1];if(sum>=(r2-r1+1)*(c2-c1+1))cout<<"Yes"<<endl;// 为了保险，用了大于等于elsecout<<"No"<<endl;}}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
