#P1392. [CEOI2008]Dominance

    ID: 404 传统题 1000ms 512MiB 尝试: 67 已通过: 30 难度: 7 上传者: 标签>CF2200提高+/省选-坐标变换奇偶分组向下取整与向上取整半开区间统一离散化扫描线添加/删除事件

[CEOI2008]Dominance

[CEOI2008] Dominance

题目描述

给出一个宽为 WW,高为 HH 的矩形 。

在它上面有两种点, blackblack 及 whitewhite。 每个点都有自己的辐射范围 rr:点 (x,y)(x,y) 能辐射到且仅辐射到满足 ∣x−x0∣+∣y−y0∣≤r|x-x_0|+|y-y_0|\le r 的整数格点 (x0,y0)(x_0,y_0)(包括边界)。所有给定辐射区域均完全位于矩形内。对于其它的点如果它受到白点的辐射多于黑色的,则为白点,反之亦然,如果相同的话则中立。

现给出白点及黑色的坐标及各自的辐射范围,问最后白色点一共有多少个,黑色点共有多少个 。

输入格式

第一行给出 WW 和 HH,左下角坐标为 (0,0)(0,0), 右上角为 (W−1,H−1)(W-1,H-1)。

第二行给出数字 NN,代表有多少个点。

接下来 NN 行,每行先给出点的属性,再给出坐标,再给出辐射范围(在 [0,5×108)[0,5\times10^8) 内;所有坐标满足 0≤x<W,0≤y<H0\le x<W,0\le y<H)

输出格式

两个数,分别代表白色点有多少个,黑色点有多少个 。

样例 #1

样例输入 #1

10 10
3
W 3 6 3
B 6 4 2
W 3 3 2

样例输出 #1

30 9

提示

对于 100%100\% 的数据,1≤W,H≤1091 \le W,H \le 10^9,0≤N≤3×1030 \le N \le 3\times 10^3。


样例解释: