专栏文章

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

封封禁用户
P13596题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mio42beh
此快照首次捕获于
2025/12/02 13:01
3 个月前
此快照最后确认于
2025/12/02 13:01
3 个月前
查看原文
原题传送门

题意略

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

皮克定理

题目说白了就是求出一个格点多边形的面积，这里一个很实用的定理就是皮克定理：
S=I+B2−1S=I+\dfrac{B}{2}-1
其中，II 表示多边形内部的格点，BB 表示多边形边上的格点。
题解区里已经有大佬给出了数学证明，但在这里我想给出一个更好理解，也更有趣的做法（忽略图形中间的那条线）。

皮克定理的证明

由于本人画画能力极低，在此附上 MPLN的图片作为例子： 由于我们生活在三维空间（如果你已经被二向箔打击，请忽略），所以这个平面上是可以放东西的。
那么，现在我们要开始一场漫长的旅行了，你准备好了吗？

冰块——从数学到物理

现在让我们想象有一个 真的很闲 的人用魔法在每一个格点上放了质量为 11 的冰块。
然而这个人并没有能力维持低温，所以冰块不久就开始融化了。不久后，水就均匀铺满了整个平面，易得单位面积上的水量就是 11（因为存在格点与单位面积的一一对应，具体为每个格点对应左下角的单位面积）。
于是我们就成功把面积问题转化成了水量问题，求图形面积的问题顺理成章地变成了求水漫金山后图形内部的水量。
现在我们说明一个引理：冰融化过程中多边形内部的水量始终保持不变。
很反直觉对吧，下面我们来试着证明一下。
我们把目光聚焦在多边形的一条边上，如下图（以下图片仍然来自同一大佬）。
由于冰块都是从格点开始融化的，所以我们只需要关注格点就好了。
注意到，对于任意一个不在线段上的格点（在线段上的点同理），都一定存在另一个点，使得两个点 关于线段的中点成中心对称（注意不是轴对称）。例如上面有蓝色框的点就关于绿色线段的中点中心对称。
于是，当一个点上的冰融化后的水到达这条线时，它的对称点上的水也刚好到达。于是两边同时流进流出，净流量为 00。引理得证。
于是我们得到一个新的结论：对于一个格点多边形，它内部的水量时时刻刻都不变。
Amazing 啊！我们只需要求出最开始多边形内部的水（也就是冰）量就可以知道多边形的面积了！
下面我们分类讨论：

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

由于这些冰块所在的格点都在多边形内部，因而全部属于多边形的面积。
那么这一部分贡献的面积就是：
S1=IS_1=I

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

格点是没有大小的，然而冰块有（没错这是我选择冰块作为证明的原因只一），由于边是一条线段，处于边上的冰块都会被“割”成两半，只有一半在多边形内部。
我们假设这些格点的数量为 KK，则这些格点“贡献”的面积为：
S2=K2S_2=\dfrac{K}{2}

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

此时就需要用到角度计算了！
我们假设冰块都是圆柱体（或者圆锥、球等），第 kk 个顶点的内角（注意是多边形的内角，因为有可能是凹多边形）度数为 θk\theta_k（注意这里使用弧度制，当然你用度数也是可以的），那么这个格点中的冰块属于多边形的量就是：
S3,k=1×θk2π=θk2πS_{3,k}=1\times\dfrac{\theta_k}{2\pi}=\dfrac{\theta_k}{2\pi}
我们假设多边形顶点上有 VV 个格点，那么这个多边形是一个 VV 边形，同时满足：
V+K=BV+K=B
那么这种情况下所贡献的面积就是：
S3=∑i=1VS3,i=∑i=1Vθi2π=12π∑i=1Vθi\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}
又因为 VV 边形的内角和为 (V−2)×π(V-2)\times\pi，所以上式又可以表示成：
S3=12π×(V−2)×π =V2−1\begin{aligned} S_3&=\dfrac{1}{2\pi} \times(V-2)\times\pi\\ \ \\ &=\dfrac{V}{2}-1 \end{aligned}

整合——欢迎回来

最后，我们把三个部分所贡献的面积相加，得到：
S=S1+S2+S3=I+K2+V2−1=I+B2−1\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 本题需要询问矩形总面积不得超过 11，而我们有 100×100=104100\times100=10^4 个点，因此每次询问的矩形（此处用正方形更加简单，因此下文使用“正方形”）大小不得大于 0.00010.0001，正方形的边长不得大于 0.010.01。
因此我们只需询问 10410^4 次，每次用正方形套住一个格点就行啦！得到的返回值有一下三种可能：
  • S′=0.0001S'=0.0001，那么这个这个点在多边形内部，I←I+1I\gets I+1；
  • 0<S′<0.00010<S'<0.0001，那么这个点在多边形边界上，B←B+1B\gets B+1；
  • S′=0S'=0，那么这个点在多边形外部。
最后用皮克定理算出面积输出就好啦！
记得 double 类型要设置 eps 判断。

AC Code（c++）

CPP
#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);
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...