题解：P13596 『GTOI - 1C』Top Miner

· · 题解

原题传送门

题意略

特别注意：矿脉的顶点都在整数坐标（也叫格点）上，同时如果你想拿到满分，你询问的矩形总面积不能超过 1。

皮克定理

题目说白了就是求出一个格点多边形的面积，这里一个很实用的定理就是皮克定理：

S=I+\dfrac{B}{2}-1

其中，I 表示多边形内部的格点，B 表示多边形边上的格点。

题解区里已经有大佬给出了数学证明，但在这里我想给出一个更好理解，也更有趣的做法（忽略图形中间的那条线）。

皮克定理的证明

由于本人画画能力极低，在此附上 @MPLN 的图片作为例子： 由于我们生活在三维空间（如果你已经被二向箔打击，请忽略），所以这个平面上是可以放东西的。

那么，现在我们要开始一场漫长的旅行了，你准备好了吗？

冰块——从数学到物理

现在让我们想象有一个 真的很闲 的人用魔法在每一个格点上放了质量为 1 的冰块。

然而这个人并没有能力维持低温，所以冰块不久就开始融化了。不久后，水就均匀铺满了整个平面，易得单位面积上的水量就是 1（因为存在格点与单位面积的一一对应，具体为每个格点对应左下角的单位面积）。

于是我们就成功把面积问题转化成了水量问题，求图形面积的问题顺理成章地变成了求水漫金山后图形内部的水量。

现在我们说明一个引理：冰融化过程中多边形内部的水量始终保持不变。

很反直觉对吧，下面我们来试着证明一下。

我们把目光聚焦在多边形的一条边上，如下图（以下图片仍然来自同一大佬）。

由于冰块都是从格点开始融化的，所以我们只需要关注格点就好了。

注意到，对于任意一个不在线段上的格点（在线段上的点同理），都一定存在另一个点，使得两个点 关于线段的中点成中心对称（注意不是轴对称）。例如上面有蓝色框的点就关于绿色线段的中点中心对称。

于是，当一个点上的冰融化后的水到达这条线时，它的对称点上的水也刚好到达。于是两边同时流进流出，净流量为 0。引理得证。

于是我们得到一个新的结论：对于一个格点多边形，它内部的水量时时刻刻都不变。

Amazing 啊！我们只需要求出最开始多边形内部的水（也就是冰）量就可以知道多边形的面积了！

下面我们分类讨论：

内部的冰块——完整地留下

由于这些冰块所在的格点都在多边形内部，因而全部属于多边形的面积。

那么这一部分贡献的面积就是：

S_1=I

边上的冰块（不包括顶点）——一刀切开

格点是没有大小的，然而冰块有（没错这是我选择冰块作为证明的原因只一），由于边是一条线段，处于边上的冰块都会被“割”成两半，只有一半在多边形内部。

我们假设这些格点的数量为 K，则这些格点“贡献”的面积为：

S_2=\dfrac{K}{2}

顶点上的冰块——转动的角与 \pi

此时就需要用到角度计算了！

我们假设冰块都是圆柱体（或者圆锥、球等），第 k 个顶点的内角（注意是多边形的内角，因为有可能是凹多边形）度数为 \theta_k（注意这里使用弧度制，当然你用度数也是可以的），那么这个格点中的冰块属于多边形的量就是：

S_{3,k}=1\times\dfrac{\theta_k}{2\pi}=\dfrac{\theta_k}{2\pi}

我们假设多边形顶点上有 V 个格点，那么这个多边形是一个 V 边形，同时满足：

V+K=B

那么这种情况下所贡献的面积就是：

\begin{aligned} S_3&=\sum_{i=1}^{V}S_{3,i}\\ &=\sum_{i=1}^{V}\dfrac{\theta_i}{2\pi}\\ &=\dfrac{1}{2\pi}\sum_{i=1}^{V}\theta_i \end{aligned}

又因为 V 边形的内角和为 (V-2)\times\pi，所以上式又可以表示成：

\begin{aligned} S_3&=\dfrac{1}{2\pi} \times(V-2)\times\pi\\ \ \\ &=\dfrac{V}{2}-1 \end{aligned}

整合——欢迎回来

最后，我们把三个部分所贡献的面积相加，得到：

\begin{aligned} S&=S_1+S_2+S_3\\ &=I+\dfrac{K}{2}+\dfrac{V}{2}-1\\ &=I+\dfrac{B}{2}-1 \end{aligned}

于是皮克定理得证。

怎么样，你回来了吗？

本题解法

没错！我们只需要一次用矩形框住一个点就好了！

由于 AC 本题需要询问矩形总面积不得超过 1，而我们有 100\times100=10^4 个点，因此每次询问的矩形（此处用正方形更加简单，因此下文使用“正方形”）大小不得大于 0.0001，正方形的边长不得大于 0.01。

因此我们只需询问 10^4 次，每次用正方形套住一个格点就行啦！得到的返回值有一下三种可能：

最后用皮克定理算出面积输出就好啦！

记得 double 类型要设置 eps 判断。

AC Code（c++）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; // 此处套用头文件，请忽略
typedef double db;

const db eps = 1e-9; // 避免精度误差
db a,B,I;

int main(){
    for (db x = 0; x <= 99; x = x + 1.0) for (db y = 0; y <= 99; y = y + 1.0) {
        printf("? %.3lf %.3lf %.3lf %.3lf %.3lf %.3lf %.3lf %.3lf"
            , x - 0.005, y - 0.005
            , x + 0.005, y - 0.005
            , x + 0.005, y + 0.005
            , x - 0.005, y + 0.005); // 框正方形
        cout << endl; // 好像能自动清空缓存，有点忘了
        cin >> a;
        if (abs(a - 0.0001 ) <= eps)
            I = I + 1.0;
        else if(abs(a) >= eps)
            B = B + 1.0;
    }
    printf("! %.1lf", I + B / 2 - 1);
}