题解：P13596 『GTOI - 1C』Top Miner
MPLN
·
·
题解
我就猜有人没听说过神秘的 Pick 定理，所以这里给大家证明一下，会的可以跳过至本题做法部分。
Pick 定理
前言：这个定理我曾经想出来过一种代数硬算的推导，虽然直观但是过于复杂就不写了。这里我们考虑用数学归纳法证明，部分内容借鉴了 wikipedia 和 百度百科 的相关资料。
下称格点为网格图中的横竖线交点，或平面直角坐标系中横坐标与纵坐标均为整数的点。
Pick 定理是一个极为巧妙的定理，当我们有一张网格图，在上面随便画一个简单多边形，只要所有顶点都在网格格点上，数个数就能算出多边形面积！
那么具体怎么数呢？
让我们随便画一个多边形：
我们需要注意两个数：
- 这个多边形内部有多少个格点，图中用绿色点标出，共 8 个，记为 I。
- 这个多边形边上有多少个格点，图中用蓝色点标出，共 11 个，记为 B。
所以，多边形面积 S=I+\frac{B}{2}-1=8+\frac{11}{2}-1=12.5。
公式就是：
S=I+\frac{B}{2}-1
简化问题
数学归纳法是个神奇的东西，我们像递归一样把大问题简化，变成一个个小问题，于是可以轻松解决。
在多边形中，简化问题最方便的就是把多边形分割成一个个三角形。那么这里考虑把 n 边形拆成一个 n-1 边形和一个三角形：
红色的点代表这个三角形和 n-1 边形边上的共格点数。
设三角形内部格点数为 I_{\triangle}，边上格点数为 B_{\triangle}，面积为 S_{\triangle}。n-1 边形内部格点数为 I_1，边上格点数为 B_1，面积为 S_1。它们共边上的格点数（红色点）为 c。
如果三角形和 n-1 边形都满足 Pick 定理，即：
S_{\triangle}=I_{\triangle}+\frac{B_{\triangle}}{2}-1\\
S_{1}=I_{1}+\frac{B_{1}}{2}-1
则总面积 S_0 为：
\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_{\triangle}+I_{1}+c-2 不就是大多边形内部格点数，B_{\triangle}+B_{1}-2c+2 不就是大多边形边上格点数嘛！（减掉两遍内部的那条边，再把边的左右端点加回来）。所以大多边形也符合 Pick 定理。
至此，我们得到了这个推论：
对于一个简单多边形 P，和与其有一条共边的三角形 T，若 P,T 都符合 Pick 定理，则拼接形成的简单多边形 PT 也符合 Pick 定理。（其中 P 与 T 没有重叠部分）
因为所有简单多边形都可以分割成若干个任意三角形，那么我们只需要证明 Pick 定理对于任意三角形成立，不就说明了对于任意多边形成立！
为了达到这一目的，我们先来看矩形和直角三角形……
矩形（长方形）
对于一个正着放的（边和坐标轴平行）的矩形，它应当是符合皮克定理的，这很好证明。
设相邻格点距离为 1，若矩形的长为 l，宽为 w，则边上格点数 B=2l+2w，内部格点数 I=(l-1)(w-1)，面积为 S=lw。
很显然有：
S=lw=(l-1)(w-1)+\frac{2l+2w}{2}-1=I+\frac{B}{2}-1
就证完了，符合 Pick 定理。
直角三角形
对于一个直角边和坐标轴平行的直角三角形，它应当是符合皮克定理的，我们可以把矩形切一半来证明。
设相邻格点距离为 1，若矩形的长为 l，宽为 w，则三角形面积为 S_{\triangle}=\frac{lw}{2}。
设图中直角三角形斜边多覆盖的内部格点数量为 c（红色点）。
那么直角三角形内部格点数为 I=\frac{(l-1)(w-1)-c}{2}，边上格点数为 B=l+w+c+1。
可以得到：
\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 定理。
任意三角形
还记得我们的推论吗？
对于一个简单多边形 P，和与其有一条共边的三角形 T，若 P,T 都符合 Pick 定理，则拼接形成的简单多边形 PT 也符合 Pick 定理。
这个命题反过来也可以用：
对于一个简单多边形 P，和与其有一条共边的三角形 T，若 P 和 PT 都符合 Pick 定理，则 T 也符合 Pick 定理。
为什么？把之前的证明反过来算一遍，等式自然也是成立的。
既然已经证明了矩形和直角三角形符合 Pick 定理，又有这个美妙的结论，为何不从矩形中挖掉几个直角三角形来得到任意三角形呢？因为这样这个三角形也会符合 Pick 定理！
在这个过程中，矩形就是那个 PT，直角三角形就是 T，所以一步步挖掉后每次得到的新多边形 P 都符合 Pick 定理，直到 P 为我们要求的某个三角形。
这是锐角三角形的情况。
这是钝角三角形的情况。
至此，我们避开了运算，直接推出了结果。
所以，任意三角形都是符合 Pick 定理的。
而多边形是任意三角形的拼接，也符合 Pick 定理。
说了这么多，终于可以愉快地写下证毕二字！
总结
最后再放一遍 Pick 定理：
给定顶点均为整点的简单多边形，皮克定理说明了其面积
$I$、边上格点数目
$B$ 的关系：
$$
S=I+\frac{B}{2}-1
$$
其实 Pick 定理的题目大多还是挺套路的，但有的时候会和较为复杂的计算几何算法相结合，但是那样的话难点就与定理本身无关了。
## 本题做法
出题人给了一个挖矿的神奇背景，目标是在 $100\times 100$ 网格中求出一个未知多边形的面积（多边形所有顶点都是格点）。可以询问最多 $10^4$ 个矩形，并获得这个矩形与多边形交集的面积。
对于询问的要求非常极限，所有询问矩形的大小不能超过 $1$ 才能 AC。询问的矩形边长不得小于 $0.01$。
相信知道皮克定理的你一定会做了，不就是用这个公式算嘛！
$$
S=I+\frac{B}{2}-1
$$
我们直接枚举所有的格点（共 $10^4$ 个），判断这个格点是在多边形内部、在多边形边上、还是在多边形外面即可。
那么就直接询问一个边长为 $0.01$ 的正方形，刚好套住格点不就好啦！如果获得的面积 $S'=0.0001$（正方形面积），那么这个格点就在多边形内部；如果 $0<S'<0.0001$，那么这个格点就在多边形边上；如果 $S'=0$，那么这个格点就在多边形外面。
因为回答可能会有 $10^{-9}$ 的误差，所以记得设个 eps 判断。
这样统计出 $I$、$B$ 之后直接算即可。这样总询问面积为 $(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;
}
```
如果有任何疑问或觉得讲的不清楚的地方，欢迎留言！
~~如果没有，点赞。~~