ZROI P2592 题解

题面

点击此处展开题面

六边形战士

众所周知，六边形可以对平面进行密铺。

对于密铺的图形建立平面直角坐标系，其中原点在某个六边形的正中间，每个六边形的边长为 1。现在给定 $T$ 组询问，每组询问包含 $x_1, y_1, x_2, y_2$，分别表示长方形的左下角和右上角，保证 $x_1 < x_2,y_1 < y_2$，你需要求出这个长方形中包含了多少个完整的六边形。

输入格式

第一行输入一个正整数 $T$ 表示询问个数。

接下来 $T$ 行每行四个整数 $x_1,y_1,x_2,y_2$。

输出格式

输出 $T$ 行，每行一个非负整数表示答案。

样例

输入：

4
-1 -1 1 1
0 0 5 5
-500 -500 500 500
-1000000000 -1000000000 1000000000 1000000000

输出：

1
4
383373
1539600716281766487

数据范围

• 测试点 1~2、5~6：$T \leq 10$
• 测试点 3~4、7~10：$T \leq 10^5$

记 $m$ 为 $|x_1|,|y_1|,|x_2|,|y_2|$ 的最大值。

• 测试点 1~4：$m \leq 500$
• 测试点 5~7：$m \leq 10^5$
• 测试点 8~10：$m \leq 10^9$

解题

首先分析图形：

考虑把每个图形缩成一个点，把区域缩半个图形的大小，统计在区域中的点的数量即可。

对于在横轴上有初始偏移（$x+\frac{1}{2}$）的行，计算时相应偏移区域（$x+\frac{1}{2}$）即可。

代码

#include <cmath>
#include <iostream>
using namespace std;
typedef long long LL;

const double S3 = sqrt(3.0);

inline LL count(double l, double r) {
  return max(0ll, LL(floor(r) - ceil(l) + 1));
}

int main() {
  int t;
  scanf("%d", &t);
  LL x1, y1, x2, y2, a, b, ans;
  while (t--) {
    scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
    // 横排无偏移
    a = count(x1 / S3 + 0.5, x2 / S3 - 0.5);    // 横排
    b = count((y1 + 1) / 3.0, (y2 - 1) / 3.0);  // 竖排
    ans = a * b;
    // 横排有偏移
    a = count(x1 / S3, x2 / S3 - 1);                        // 横排
    b = count((y1 + 1) / 3.0 - 0.5, (y2 - 1) / 3.0 - 0.5);  // 竖排
    ans += a * b;
    printf("%lld\n", ans);
  }
  return 0;
}