14 人解决,20 人已尝试。
15 份提交通过,共有 78 份提交。
5.7 EMB 奖励。
单点时限: 1.0 sec
内存限制: 512 MB
实时阴影是电子游戏中最为重要的画面效果之一。在计算机图形学中,通常使用阴影映射方法来实现实时阴影。
游戏开发部正在开发一款 2D 游戏,同时希望能够在 2D 游戏中模仿 3D 游戏的光影效果,请帮帮游戏开发部!
给定 x-y 平面上的 $n$ 个矩形,矩形的边界平行于坐标轴,且可能相互重叠。同时给定点光源的坐标。现有 $m$ 次操作,每次操作添加或删除一个矩形,或询问 $x$ 轴上的一点是否在阴影内。
第一行,两个整数 $n, m (1\leq n, m \leq 2\times 10^5)$。
第二行,两个整数 $l_x, l_y$,表示光源的坐标为 $(l_x, l_y)$。$|l_x|\leq 2\times 10^5, 0 < l_y\leq 2\times 10^5$。
接下来 $n$ 行,每行 $5$ 个整数 $id, x, y, w, h$,表示编号为 $id$ 的矩形,左下角坐标为 $(x, y)$,宽为 $w$,高为 $h$。
接下来 $m$ 行,每行先输入一个正整数 $opt\in [1, 3]$。
$1 \leq id \leq 4\times 10^5$
$|x|\leq 2\times 10^5, 0 < y \leq 2\times 10^5$
$0 < w, h \leq 2\times 10^5$
$|p| \leq 10^9$
保证任意时刻场景中所有矩形的 $id$ 互不相同。保证所有矩形各个顶点的 $y$ 坐标一定严格小于光源的 $y$ 坐标。若询问点在阴影的边界上,仍算作在阴影内。
对于每个 $opt = 3$ 的询问,若询问的点在阴影中,则输出一行 YES
,否则输出一行 NO
。
3 19 4 7 1 1 1 2 1 2 6 1 2 3 3 5 2 4 1 3 -1 3 0 3 2 3 3 3 4 3 5 3 6 3 12 3 13 3 14 1 4 4 5 2 1 3 3 3 4 3 5 3 18 3 19 2 1 3 2 3 3
NO YES YES NO NO NO YES YES YES NO NO YES YES YES NO NO NO
在进行所有修改操作之前,所有矩形的位置如下 (绿色部分为阴影区域):
在加入一个矩形后,所有矩形的位置如下:
在删除一个矩形后,所有矩形的位置如下:
14 人解决,20 人已尝试。
15 份提交通过,共有 78 份提交。
5.7 EMB 奖励。
创建: 4 月,3 周前.
修改: 4 月,3 周前.
最后提交: 3 月,2 周前.
来源: N/A