题解：P13938 [EC Final 2019] City

· · 题解

题意

给定一个 n \times m 的网格，问有多少条线段，使得该线段两端点在网格点上，且该线段中点也在网格点上。

思路

由于线段可以斜着画，所以我们不妨枚举所有网格点，求出以该网格点为中点的所有满足条件的线段数量。

我们以下图的红点为例，可以发现，如果以该红点为中点，那么可以构造出的线段的最大宽度为 6 格，最大高度为 6 格。

因此，我们可以构造出如下图的部分线段(如蓝色的线所示)。

上图线段数量的计算方式也很简单，我们设从中点横向延伸的长度(即线段最大宽度的一半)为 w，纵向延伸的长度(最大高度的一半)为 h。那么上面三个图的线段数量即为 h \times (2w + 1)。

同时，我们还需要加上没有纵向延伸的线段，显然，仅横向的线段数量就是 w。

因此，以该点为中点的线段总数为 h \times (2w + 1) + w，累加在 ans 中即可。

那么如何计算 w 和 h 呢？从该点开始左右或上下延伸，一旦碰到了边界，那么该延伸长度就是 w 和 h。

若假设网格左上角的点为 (1, 1)，右下角为 (m + 1, n + 1)，那么显然，对于一个网格点 (i, j)，有 w = \min\{i - 1, m + 1 - i\}，h = \min\{j - 1, n + 1 - j\}。

由于计算结果可能很大，所以需要使用 long long。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n, m, ans = 0;
int main()
{
    scanf("%lld%lld", &n, &m);
    for(ll i = 1;i <= n + 1;i++){
        for(ll j = 1;j <= m + 1;j++){
            // 计算 h 和 w
            ll h = min(i - 1LL, n + 1LL - i);
            ll w = min(j - 1LL, m + 1LL - j);
            ll tot = h * ((w << 1LL) + 1LL) + w; // 计算该点线段数量
            ans = ans + tot; // 累加
        }
    }
    printf("%lld", ans); // 输出
    return 0; // 结束 (｡･ω･｡)
}