自动搬运

查看原文

来自洛谷，原作者为

	AtomAlpaca 厌见桃株，夜来悲哭。生世徒劳，风吹烛。

搬运于2025-08-24 22:02:30，当前版本为作者最后更新于2023-06-09 13:33:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

link

简述题意：在平面直角网格图上，给出一个每个顶点都是整点的任意多边形，求出严格在多边形内部的网格的长度的总和。

题解

我们首先拿第一张图片举例。

将这个图形沿竖直方向的网格线划分为若干个梯形（或三角形）。根据梯形的面积公式，每个梯形的面积都是它相邻的两条截线的长度和的一半，因此整个多边形的面积就是竖直方向所有截线长度的和。横向的长度也是同样地处理。

但上述方法我们显然少考虑了一种情况。如图二：

其中标为紫色的线段也属于上述计算范围内的“截线”，但是这些线段并不严格在多边形内。我们考虑去掉这部分对答案的贡献。

我们发现，这样的线段一定是且仅是多边形上与网格线重合的边，这样的边一定有一侧是多边形内侧，一侧是多边形外侧，因此划分计算面积时一定只对一个梯形(三角形)的面积产生贡献，也就是对答案造成了该线段长度的一半的贡献。因此我们只要从答案中减去这样的边的长度的一半即可。

综上，我们得到最终答案是该多边形面积的两倍减去与网格线平行的边长度和的一半。

另：题面里第一张图片并不是第一个样例的配图

代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;

typedef long long ll;
const ll MAX = 1e5 + 5;
ll n, x[MAX], y[MAX], S;

int main()
{
  cin >> n;
  for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i]; }
  x[0] = x[n]; y[0] = y[n];
  for (int i = 1; i <= n; ++i) { S += (x[i] * y[i - 1]) - (x[i - 1] * y[i]); }
  double ans = std::fabs(S);
  for (int i = 1; i <= n; ++i)
  {
    if (x[i] == x[i - 1]) { ans -= std::fabs(1.0 * (y[i] - y[i - 1]) / 2.0); }
    if (y[i] == y[i - 1]) { ans -= std::fabs(1.0 * (x[i] - x[i - 1]) / 2.0); }
  }
  cout << std::fixed << std::setprecision(6) << ans;
  return 0;
}