[SNCPC2024] 窗花

题目描述

有一扇 \(100 \text{cm} \times 100 \text{cm}\) 的窗户和 \(n\) 个对角线长为 \(2 \text{cm}\) 的正方形窗花。建立坐标系，以窗户左下角的坐标为原点 \((0,0)\)，右上角坐标为 \((100,100)\)，第 \(i\) 个窗花中心被贴在非边缘的整坐标点 \((x_i,y_i)\) (\(1 \leq x_i,y_i \leq 99\)) 上，窗花的对角线与坐标轴平行。

问窗户有多大的面积被至少一片窗花覆盖。

输入格式

第一行一个整数 \(n\) (\(1 \leq n \leq 10000\))。

接下来 \(n\) 行，每行两个整数 \(x_i,y_i\) (\(1 \leq x_i,y_i \leq 99\))，含义如上所述。

输出格式

输出仅一行一个实数，为被至少一片窗花覆盖的面积。

你的答案被认为正确当且仅当其相对误差或绝对误差不超过 \(10^{−4}\)。形式化地说，假设你的答案是 \(a\)，标准答案是 \(b\)。你的答案被认为正确当且仅当 \(\frac{|a−b|}{\max (1,|b|)} \leq 10^{−4}\)。

样例 #1

样例输入 #1

5
1 1
2 1
3 2
5 5
5 5

样例输出 #1

7.5

提示

对于第一个样例的解释如图：

思路

#include<bits/stdc++.h>
using namespace std;
int n;
double ans = 0;
bool g[110][110];
int dis[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main(){
	scanf("%d",&n);
	ans = n * 2.0;
	for(int i = 1,x,y;i <= n;i ++){
		scanf("%d %d",&x,&y);
		if(g[x][y]){
			ans -= 2.0;
		}else{
			for(int j = 0;j < 4;j ++){
				if(g[x + dis[j][0]][y + dis[j][1]]){
					ans -= 0.5;
				}
			}
		}
		g[x][y] = 1;
	}
	printf("%f\n",ans);
	return 0;
}