luogu#P7865. 「EVOI-RD1」无人机航拍

「EVOI-RD1」无人机航拍

题目背景

T 市举行活动需要拍摄高空俯瞰图,找来了一个无人机机队负责拍摄工作。 一E孤行 是队伍的队长,他根据广场的规模来安排无人机的位置。

题目描述

有一个广场,可以看做是一个 n×mn \times m 的矩形;一E孤行 一共有 ss 架无人机,每架无人机的拍摄范围也可以看做是一个矩形,无人机机队的拍摄范围为所有无人机拍摄范围的并。

一E孤行 负责安排无人机的位置,而总负责人 WuuTue 要验收他的方案。WuuTue 的验收方法是列举出 LL 个重要的区域,每个重要区域也是一个矩形。 一E孤行 方案的优秀程度取决于有多少个重要区域完全在无人机机队的拍摄范围中。

因此,对于每一个重要区域, 一E孤行 想知道它是否完全在无人机机队的拍摄范围中。

输入格式

第一行,用空格隔开的两个整数 nnmm,用来描述广场的大小。

第二行,一个整数 ss,表示无人机队伍中无人机的总数量。

第三行到第 s+2s+2 行,每行四个用空格隔开的整数,a1,b1,a2,b2a_1,b_1,a_2,b_2,用来描述一架无人机的拍摄范围。其中 a1,b1a_1,b_1 表示矩形的左下角坐标,a2,b2a_2,b_2 表示右上角的坐标。

s+3s+3 行,一个整数 LL,表示活动总负责人列出的重要区域的数量 LL

最后 LL 行,每行四个用空格隔开的整数 r1,c1,r2,c2r_1,c_1,r_2,c_2,用来描述一个重要区域。其中 r1,c1r_1,c_1 表示矩形区域左下角坐标,r2,c2r_2,c_2 表示右上角坐标。

输出格式

输出 LL 行,对于每个重要区域,如果完全在机队的拍摄范围内就输出 Yes,否则出 No。每个答案占一行。

9 9 
3 
2 1 4 4 
2 5 4 9 
5 2 7 6 
2 
3 3 6 6 
5 6 8 8
Yes 
No

提示

样例说明

如下图所示,区域 A,B,CA,B,C 分别是某某安排的无人机能够覆盖的范围,区域 D,ED,E 是 WuuTue 要验收时列举的重点区域,区域 DD 能够被完全覆盖,区域 EE 不能被全部覆盖。

数据规模与约定

本题采用捆绑测试。

对于 40%40\% 的数据:1n10001 \le n \le 10001s1001 \le s \le 100
对于 100%100\% 的数据:

  • 1n,m3×1031 \le n, m \le 3 \times 10^{3}
  • 1s,L1061 \le s,L \le 10^6
  • 1x1<x2n1 \le x_1 < x_2 \le n
  • 1r1<r2n1 \le r_1 < r_2 \le n
  • 1y1<y2m1 \le y_1 < y_2 \le m
  • 1c1<c2m1 \le c_1 < c_2 \le m