#2925. [GDKOI]Macaron

[GDKOI]Macaron

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出 nmn ∗ m 的一块二维平面作为 NanaNana 的家,左上角墙角为 (0,0){(0,0)} ,右下角墙角为 (n+1,m+1){(n+1, m+1)}。其中 家里有 kk 个家具,每个家具会占其中一个点,题目将会给出每个家具的坐标。

马卡龙是一只扫地机器人,半径为r r 的圆形的它可以向上下左右四个方向移动,移动前后必须保持圆心 在整点上,并且不能穿过家具或外墙进行打扫,即身躯不可以与家具或墙壁有重合部分(允许相切)。它初始 圆心位置为 (xs,ys)(x_s, y_s) ,将会从此出发,打扫它能到达的区域。

马卡龙想知道自己可以打扫到多大面积。你只需要告诉马卡龙,它出发后它的圆心可以到达的平面内的 整点数量。

对了,你只用将答案告诉马卡龙就够了,不需要告诉 NanaNana ,因为马卡龙不希望伤心的 NanaNana 会为这些 琐事烦心。

输入格式

第一行有两个整数 n,mn, m ,表示 NanaNana 的家的大小。

第二行有一个整数 r2r^2 ,表示马卡龙半径的平方。

第三行有两个整数 xs,ys{x_s, y_s} ,表示马卡龙出发的位置,保证在其初始位置上,马卡龙不会与家具有重合部 分。

第四行有一个整数 kk,接下来kk行里每行给出两个整数x,yx, y ,表示其中一个家具的坐标。

输出格式

仅一个整数 ansans ,表示答案。

输入样例1

10 10
5
4 5
5
7 10
6 10
5 9
4 9
4 10

输出样例1

29

输入样例2

1000 1000
3000
419 294
17
75 599
782 311
783 311
784 311
783 312
784 312
916 673
915 673
290 490
202 434
254 670
255 670
929 69
929 70
568 835
83 904
721 702

输出样例2

712414

数据范围

对所有数据满足 0knm {0 ≤ k ≤ n∗ m}, 1rmin(n2,m2){1 ≤ r ≤ min( ⌊ {\frac{n}{2} }⌋,⌊\frac{m}{2}⌋)}, 1xsn,1ysm{1 ≤ x_s ≤ n, 1 ≤ y_s ≤ m}

其中有 30%{30\%} 的数据点满足 1n,m100{1 ≤ n, m ≤ 100};

剩下 70%{70\%} 的数据点满足 1n,m1000{1 ≤ n, m ≤ 1000}

2023GDKOI普及组day1 重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-12-23 14:30
结束于
2024-1-5 2:30
持续时间
300 小时
主持人
参赛人数
22