专栏文章

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

海海洋守卫者
P13596题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miohzzhu
此快照首次捕获于
2025/12/02 19:31
3 个月前
此快照最后确认于
2025/12/02 19:31
3 个月前
查看原文

P13596 『GTOI - 1C』Top Miner

题目定位 『诈骗题』

解题思路

看前须知：皮克定理
感觉知道了这个定理剩下的也没什么好说的了。
皮克定理：一个简单多边形，顶点均在格点上，内部格点数目为 II、边上格点数目为 BB，则其面积 S=I+B2−1S=I+\frac{B}{2}-1。
我们可以在每个顶点处询问一个小正方形覆盖的面积，若正好等于小正方形的面积则内部格点数目加一，否则若不为 00，边上格点数目加一。

完整代码

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

评论

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

正在加载评论...