打卡信奥刷题（3166）用C++实现信奥题 P7865 「EVOI-RD1」无人机航拍

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 s2s2行每行四个用空格隔开的整数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 s3s3行一个整数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输入 #19 9 3 2 1 4 4 2 5 4 9 5 2 7 6 2 3 3 6 6 5 6 8 8输出 #1Yes 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≤10001 ≤ 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实现#includeiostream#includealgorithm#defineMAXN3005#defineMAXM3005#defineMAXS1000005usingnamespacestd;intn,m,s,l;intsqu[MAXN][MAXM];// 使用一个矩阵即可intmain(){std::ios::sync_with_stdio(false);cinnms;for(inti1;is;i){inta1,b1,a2,b2;cina1b1a2b2;squ[a1][b1];squ[a21][b21];squ[a21][b1]--;squ[a1][b21]--;}for(inti1;in;i){for(intj1;jm;j){squ[i][j]squ[i-1][j]squ[i][j-1]-squ[i-1][j-1];}}for(inti1;in;i){for(intj1;jm;j){if(squ[i][j])squ[i][j]1;}}for(inti1;in;i){for(intj1;jm;j){squ[i][j]squ[i-1][j]squ[i][j-1]-squ[i-1][j-1];}}cinl;for(inti1;il;i){intr1,c1,r2,c2;cinr1c1r2c2;intsumsqu[r2][c2]-squ[r1-1][c2]-squ[r2][c1-1]squ[r1-1][c1-1];if(sum(r2-r11)*(c2-c11))coutYesendl;// 为了保险用了大于等于elsecoutNoendl;}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容