Managing Telephone Poles

题意翻译

## 题意 平面上有一些点，由大小为 $(n + 1) \times (m + 1)$ 的网格 $a$ 表示。如果 $a_{x, y} = 1$，则在 $(x, y)$ 处有一个点。 对于每个点 $(x, y)$，将 $S(x, y)$ 定义为离这个点最近的点和 $(x,y)$ 之间欧氏距离的平方。形式上，两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的欧氏距离的平方是 $(x_2 - x_1)^2 + (y_2 - y_1)^2$。 为了优化平面图，项目主管会询问每个 $0 \leq x \leq n$ 和 $0 \leq y \leq m$ 的所有 $S(x,y)$ 的总和。需要通过查找 $\sum_{x=0}^{n} {\sum_{y=0}^{m}{S(x,y)}}$ 的值来帮助他。 ## 输入 第一行包含两个整数 $n$ 和 $m$ ($0\leq n,m<2000$)——网格的大小。 接着是 $n+1$ 行，每行包含 $m+1$ 个整数 $a_{i,j}$( $0\leq a{i,j}\leq1)$ ——表示点在平面中位置的网格。给定平面图中至少有一个点。 ## 输出 输出一个整数，表示 $ \sum_{x=0}^{n}{ \sum_{y=0}^{m}{S(x,y)}} $。 ## 样例解释 在第一个示例中，点（0,0）、（1,0）、（2,0）、（0,1）、（1,1）和（2,1）的最近的点位于（0,0）。而点（0,2）、（1,2）和（2,2）的最近的点位于（0,2）。因此，$\sum_{x=0}^{n}{\sum_{y=0}^{m}{S(x，y)}}=(0+1+4)+(1+2+5)+(0+1+4)=18$。

题目描述

Mr. Chanek's city can be represented as a plane. He wants to build a housing complex in the city. There are some telephone poles on the plane, which is represented by a grid $ a $ of size $ (n + 1) \times (m + 1) $ . There is a telephone pole at $ (x, y) $ if $ a_{x, y} = 1 $ . For each point $ (x, y) $ , define $ S(x, y) $ as the square of the Euclidean distance between the nearest pole and $ (x, y) $ . Formally, the square of the Euclidean distance between two points $ (x_1, y_1) $ and $ (x_2, y_2) $ is $ (x_2 - x_1)^2 + (y_2 - y_1)^2 $ . To optimize the building plan, the project supervisor asks you the sum of all $ S(x, y) $ for each $ 0 \leq x \leq n $ and $ 0 \leq y \leq m $ . Help him by finding the value of $ \sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 0 \leq n, m < 2000 $ ) — the size of the grid. Then $ (n + 1) $ lines follow, each containing $ (m + 1) $ integers $ a_{i, j} $ ( $ 0 \leq a_{i, j} \leq 1 $ ) — the grid denoting the positions of telephone poles in the plane. There is at least one telephone pole in the given grid.

输出格式

Output an integer denoting the value of $ \sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} $ .

输入输出样例

输入样例 #1

2 2
101
000
000

输出样例 #1

18

输入样例 #2

5 4
10010
00000
01000
00001
00100
00010

输出样例 #2

36

说明

In the first example, the nearest telephone pole for the points $ (0,0) $ , $ (1,0) $ , $ (2,0) $ , $ (0,1) $ , $ (1,1) $ , and $ (2,1) $ is at $ (0, 0) $ . While the nearest telephone pole for the points $ (0, 2) $ , $ (1,2) $ , and $ (2,2) $ is at $ (0, 2) $ . Thus, $ \sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} = (0 + 1 + 4) + (1 + 2 + 5) + (0 + 1 + 4) = 18 $ .

题意翻译

## 题意 平面上有一些点，由大小为 $(n + 1) \times (m + 1)$ 的网格 $a$ 表示。如果 $a_{x, y} = 1$，则在 $(x, y)$ 处有一个点。 对于每个点 $(x, y)$，将 $S(x, y)$ 定义为离这个点最近的点和 $(x,y)$ 之间欧氏距离的平方。形式上，两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的欧氏距离的平方是 $(x_2 - x_1)^2 + (y_2 - y_1)^2$。 为了优化平面图，项目主管会询问每个 $0 \leq x \leq n$ 和 $0 \leq y \leq m$ 的所有 $S(x,y)$ 的总和。需要通过查找 $\sum_{x=0}^{n} {\sum_{y=0}^{m}{S(x,y)}}$ 的值来帮助他。 ## 输入 第一行包含两个整数 $n$ 和 $m$ ($0\leq n,m<2000$)——网格的大小。 接着是 $n+1$ 行，每行包含 $m+1$ 个整数 $a_{i,j}$( $0\leq a{i,j}\leq1)$ ——表示点在平面中位置的网格。给定平面图中至少有一个点。 ## 输出 输出一个整数，表示 $ \sum_{x=0}^{n}{ \sum_{y=0}^{m}{S(x,y)}} $。 ## 样例解释 在第一个示例中，点（0,0）、（1,0）、（2,0）、（0,1）、（1,1）和（2,1）的最近的点位于（0,0）。而点（0,2）、（1,2）和（2,2）的最近的点位于（0,2）。因此，$\sum_{x=0}^{n}{\sum_{y=0}^{m}{S(x，y)}}=(0+1+4)+(1+2+5)+(0+1+4)=18$。