专栏文章

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

MMPLN
P13596题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mioia6ws
此快照首次捕获于
2025/12/02 19:39
3 个月前
此快照最后确认于
2025/12/02 19:39
3 个月前
查看原文
我就猜有人没听说过神秘的 Pick 定理，所以这里给大家证明一下，会的可以跳过至本题做法部分。

Pick 定理

前言：这个定理我曾经想出来过一种代数硬算的推导，虽然直观但是过于复杂就不写了。这里我们考虑用数学归纳法证明，部分内容借鉴了 wikipedia 和 百度百科 的相关资料。
下称格点为网格图中的横竖线交点，或平面直角坐标系中横坐标与纵坐标均为整数的点。
Pick 定理是一个极为巧妙的定理，当我们有一张网格图，在上面随便画一个简单多边形，只要所有顶点都在网格格点上，数个数就能算出多边形面积！
那么具体怎么数呢？
让我们随便画一个多边形：
我们需要注意两个数：
  1. 这个多边形内部有多少个格点，图中用绿色点标出，共 88 个，记为 II。
  2. 这个多边形边上有多少个格点，图中用蓝色点标出，共 1111 个，记为 BB。
所以，多边形面积 S=I+B2−1=8+112−1=12.5S=I+\frac{B}{2}-1=8+\frac{11}{2}-1=12.5。
公式就是：
S=I+B2−1S=I+\frac{B}{2}-1

简化问题

数学归纳法是个神奇的东西，我们像递归一样把大问题简化，变成一个个小问题，于是可以轻松解决。
在多边形中，简化问题最方便的就是把多边形分割成一个个三角形。那么这里考虑把 nn 边形拆成一个 n−1n-1 边形和一个三角形：
红色的点代表这个三角形和 n−1n-1 边形边上的共格点数。
设三角形内部格点数为 I△I_{\triangle}，边上格点数为 B△B_{\triangle}，面积为 S△S_{\triangle}。n−1n-1 边形内部格点数为 I1I_1，边上格点数为 B1B_1，面积为 S1S_1。它们共边上的格点数（红色点）为 cc。
如果三角形和 n−1n-1 边形都满足 Pick 定理，即：
S△=I△+B△2−1S1=I1+B12−1S_{\triangle}=I_{\triangle}+\frac{B_{\triangle}}{2}-1\\ S_{1}=I_{1}+\frac{B_{1}}{2}-1
则总面积 S0S_0 为：
S0=S△+S1=I△+B△2−1+I1+B12−1=I△+I1+B△+B1−22−1=I△+I1+c−2+B△+B1−2c+22−1\begin{aligned} S_{0}&=S_{\triangle}+S_1\\ &=I_{\triangle}+\frac{B_{\triangle}}{2}-1+I_{1}+\frac{B_{1}}{2}-1\\ &=I_{\triangle}+I_{1}+\frac{B_{\triangle}+B_{1}-2}{2}-1\\ &=I_{\triangle}+I_{1}+c-2+\frac{B_{\triangle}+B_{1}-2c+2}{2}-1 \end{aligned}
诶？I△+I1+c−2I_{\triangle}+I_{1}+c-2 不就是大多边形内部格点数，B△+B1−2c+2B_{\triangle}+B_{1}-2c+2 不就是大多边形边上格点数嘛！（减掉两遍内部的那条边，再把边的左右端点加回来）。所以大多边形也符合 Pick 定理。
至此，我们得到了这个推论：
对于一个简单多边形 PP，和与其有一条共边的三角形 TT，若 P,TP,T 都符合 Pick 定理，则拼接形成的简单多边形 PTPT 也符合 Pick 定理。（其中 PP 与 TT 没有重叠部分）
因为所有简单多边形都可以分割成若干个任意三角形，那么我们只需要证明 Pick 定理对于任意三角形成立，不就说明了对于任意多边形成立！
为了达到这一目的，我们先来看矩形和直角三角形……

矩形（长方形）

对于一个正着放的（边和坐标轴平行）的矩形，它应当是符合皮克定理的，这很好证明。
设相邻格点距离为 11，若矩形的长为 ll，宽为 ww，则边上格点数 B=2l+2wB=2l+2w，内部格点数 I=(l−1)(w−1)I=(l-1)(w-1)，面积为 S=lwS=lw。
很显然有：
S=lw=(l−1)(w−1)+2l+2w2−1=I+B2−1S=lw=(l-1)(w-1)+\frac{2l+2w}{2}-1=I+\frac{B}{2}-1
就证完了，符合 Pick 定理。

直角三角形

对于一个直角边和坐标轴平行的直角三角形，它应当是符合皮克定理的，我们可以把矩形切一半来证明。
设相邻格点距离为 11，若矩形的长为 ll，宽为 ww，则三角形面积为 S△=lw2S_{\triangle}=\frac{lw}{2}。
设图中直角三角形斜边多覆盖的内部格点数量为 cc（红色点）。
那么直角三角形内部格点数为 I=(l−1)(w−1)−c2I=\frac{(l-1)(w-1)-c}{2}，边上格点数为 B=l+w+c+1B=l+w+c+1。
可以得到：
I+B2−1=(l−1)(w−1)−c2+l+w+c+12−1=lw−l−w+1−c+l+w+c+12−1=lw+22−1=lw2=S△\begin{aligned} I+\frac{B}{2}-1&=\frac{(l-1)(w-1)-c}{2}+\frac{l+w+c+1}{2}-1\\ &=\frac{lw-l-w+1-c+l+w+c+1}{2}-1\\ &=\frac{lw+2}{2}-1\\ &=\frac{lw}{2}\\ &=S_{\triangle} \end{aligned}
没有问题，符合 Pick 定理。

任意三角形

还记得我们的推论吗？
对于一个简单多边形 PP，和与其有一条共边的三角形 TT，若 P,TP,T 都符合 Pick 定理，则拼接形成的简单多边形 PTPT 也符合 Pick 定理。
这个命题反过来也可以用：
对于一个简单多边形 PP，和与其有一条共边的三角形 TT，若 PP 和 PTPT 都符合 Pick 定理，则 TT 也符合 Pick 定理。
为什么？把之前的证明反过来算一遍，等式自然也是成立的。
既然已经证明了矩形和直角三角形符合 Pick 定理，又有这个美妙的结论，为何不从矩形中挖掉几个直角三角形来得到任意三角形呢？因为这样这个三角形也会符合 Pick 定理！
在这个过程中，矩形就是那个 PTPT，直角三角形就是 TT，所以一步步挖掉后每次得到的新多边形 PP 都符合 Pick 定理，直到 PP 为我们要求的某个三角形。
这是锐角三角形的情况。
这是钝角三角形的情况。
至此，我们避开了运算，直接推出了结果。
所以，任意三角形都是符合 Pick 定理的。
而多边形是任意三角形的拼接，也符合 Pick 定理。
说了这么多，终于可以愉快地写下证毕二字！

总结

最后再放一遍 Pick 定理：
给定顶点均为整点的简单多边形，皮克定理说明了其面积 SS 和内部格点数目 II、边上格点数目 BB 的关系：
S=I+B2−1S=I+\frac{B}{2}-1
其实 Pick 定理的题目大多还是挺套路的，但有的时候会和较为复杂的计算几何算法相结合，但是那样的话难点就与定理本身无关了。

本题做法

出题人给了一个挖矿的神奇背景，目标是在 100×100100\times 100 网格中求出一个未知多边形的面积（多边形所有顶点都是格点）。可以询问最多 10410^4 个矩形，并获得这个矩形与多边形交集的面积。
对于询问的要求非常极限，所有询问矩形的大小不能超过 11 才能 AC。询问的矩形边长不得小于 0.010.01。
相信知道皮克定理的你一定会做了，不就是用这个公式算嘛！
S=I+B2−1S=I+\frac{B}{2}-1
我们直接枚举所有的格点（共 10410^4 个），判断这个格点是在多边形内部、在多边形边上、还是在多边形外面即可。
那么就直接询问一个边长为 0.010.01 的正方形，刚好套住格点不就好啦！如果获得的面积 S′=0.0001S'=0.0001（正方形面积），那么这个格点就在多边形内部；如果 0<S′<0.00010<S'<0.0001，那么这个格点就在多边形边上；如果 S′=0S'=0，那么这个格点就在多边形外面。
因为回答可能会有 10−910^{-9} 的误差，所以记得设个 eps 判断。
这样统计出 II、BB 之后直接算即可。这样总询问面积为 (0.01)2×100×100=1(0.01)^2\times 100\times 100=1，刚好 100pts！
代码写起来很简单。
CPP
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
double a,B,I;
int main(){
    for(double x=0;x<=99;x=x+1){
        for(double y=0;y<=99;y=y+1){
            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;
            else if(abs(a)>=eps) B=B+1;
        }
    }
    printf("! %.1lf",I+B/2-1);
    return 0;
}
如果有任何疑问或觉得讲的不清楚的地方，欢迎留言！
如果没有，点赞。

评论

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

正在加载评论...