#P51152. 「COCI 2018.12」NLO
「COCI 2018.12」NLO
题目描述
译自 COCI 2018/2019 Contest #3 T4「NLO」
Žabnik 村已经被不明飞行物(UFO)所创造的麦田怪圈所困扰了数年。其问题主要在夏季割草的时候显现出来。
麦田是一块 行 列的格子——左上角记为坐标 ,右下角记为坐标 。一开始每块地上都有一单位的草。接下来 天,圆形的 UFO 会登录在草地上并产生一个圆圈。第 天早晨,一个半径为 的 UFO 会登陆与位于 的草地上然后将其覆盖范围内的草都“割平”。或者说,如果一块坐标为 的地满足 ,那么这块地的草的数量就会被归为 。每过一天,每块草地的数量增加 。
在第 天晚上,当地人会将剩余的草全部收割,请问他们收割的草总量是多少?
输入格式
第一行两个正整数 表示草地的行数和列数。
第二行一个正整数 表示有 UFO 经过的天数。
接下来 行,其第 行包含三个正整数 ,表示 UFO 登陆的位置以及半径。
输出格式
一个整数,输出收割的草的总量。
样例 1
6 6
3
4 4 2
3 3 2
2 4 1
68
第一天结束后:
1 1 1 1 1 1
1 1 1 0 1 1
1 1 0 0 0 1
1 0 0 0 0 0
1 1 0 0 0 1
1 1 1 0 1 1
第二天结束后:
2 2 0 2 2 2
2 0 0 0 2 2
0 0 0 0 0 2
2 0 0 0 1 1
2 2 0 1 1 2
2 2 2 1 2 2
第三天结束后:
3 3 1 0 3 3
3 1 0 0 0 3
1 1 1 0 1 3
3 1 1 1 2 2
3 3 1 2 2 3
3 3 3 2 3 3
100 100
2
50 50 49
30 30 29
9534
33333 44444
1
11111 22222 9999
1167355751
数据范围与提示
对于 的数据,保证 。
对于 的数据,保证: