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

· · 题解

P13596 『GTOI - 1C』Top Miner

题目定位 『诈骗题』

解题思路

看前须知：皮克定理

感觉知道了这个定理剩下的也没什么好说的了。

皮克定理：一个简单多边形，顶点均在格点上，内部格点数目为 I、边上格点数目为 B，则其面积 S=I+\frac{B}{2}-1。

我们可以在每个顶点处询问一个小正方形覆盖的面积，若正好等于小正方形的面积则内部格点数目加一，否则若不为 0，边上格点数目加一。

完整代码

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int I,B;
double S;
const long double eps=1e-10l;
int main(){
    for(int i=0;i<100;i++)for(int j=0;j<100;j++){
        long double x1=i-0.005,x2=i+0.005,y1=j-0.005,y2=j+0.005;
        printf("? %.3Lf %.3Lf %.3Lf %.3Lf %.3Lf %.3Lf %.3Lf %.3Lf\n",x1,y1,x1,y2,x2,y2,x2,y1);
        fflush(stdout);
        scanf("%lf",&S);
        if(fabsl(S-1e-4l)<eps)I++;
        else if(fabsl(S)>eps)B++;
    }
    printf("! %.9Lf\n",I+B/2.0l-1);
    return 0;
}