当前位置：首页 > news >正文

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

news 2026/4/26 4:05:41

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;}}