题目

编号： 201912-2

试题名称： 回收站选址

时间限制： 1.0s

内存限制： 512.0MB

题目背景

开学了，可是校园里堆积了不少垃圾杂物。
热心的同学们纷纷自发前来清理，为学校注入正能量~

题目描述

通过无人机航拍我们已经知晓了n处尚待清理的垃圾位置，其中第 $i（1\le i\le n）$处的坐标为$（x_i，y_i）$，保证所有的坐标均为整数。
我们希望在垃圾集中的地方建立些回收站。具体来说，对于一个位置$（x，y）$是否适合建立回收站，我们主要考虑以下几点：

$（x，y）$必须是整数坐标，且该处存在垃圾；
上下左右四个邻居位置，即$（x，y+1）$、$（x，y-1）$、$（x+1，y）$和$（x-1，y）$处，必须全部存在垃圾；
进一步地，我们会对满足上述两个条件的选址进行评分，分数为不大于4的自然数，表示在$（x\pm 1，y\pm 1）$四个对角位置中有几处存在垃圾。
现在，请你统计一下每种得分的选址个数。

输入格式

从标准输入读入数据。输入总共有n+1行。
第1行包含一个正整数n，表示已查明的垃圾点个数。
第1+i行$（1\le i\le n）$包含由一个空格分隔的两个整数x；和y，表示第i处垃圾的坐标。
保证输入的n个坐标互不相同。

输出格式

输出到标准输出。
输出共五行，每行一个整数，依次表示得分为0、1、2、3和4的回收站选址个数。

样例数据

样例1输入

样例1输出

样例1解释

如图所示，仅有（1，1）可选为回收站地址，评分为2。
样例2输入

1
2
3

2
0 0
-100000 10

样例2输出

样例2解释
不存在可选地址。

样例3输入

样例3输出

样例3解释
1分选址：（10，10）和（12，10）；
2分选址：（11，9）。

子任务

测试点1和2，保证对于任意的i皆满足$0\le x_i,y_i \le 2$；
测试点3、4和5，保证对于任意的i皆满足$0\le x_i,y_i \le 500$；
测试点6、7和8，保证对于任意的i皆满足$0\le x_i,y_i\le 10^9$；
测试点9和10，保证对于任意的i皆满足$|x_i|,|y_i|\le 10^9$，即坐标可以是负数。
所有的测试点保证$1\le n\le 10^3$。

提示

本题中所涉及的坐标皆为整数，且保证输入的坐标两两不同。

解答

分析

直接将坐标准换位字符串放到set中再进行判断是否存在目标点。

代码

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(int argc, char** argv) {
	
	int res[5]={0};
	set<string> s;
	long in[1001][2];
	int n;
	char buffer[255];
	
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>in[i][0]>>in[i][1];
		s.insert(string(to_string(in[i][0]))+","+string(to_string(in[i][1])));
	}
	
	for(int i=0;i<n;i++){
		if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1])))!=s.end() && 
		s.find(string(to_string(in[i][0]))+","+string(to_string(in[i][1]+1)))!=s.end() &&
		s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1])))!=s.end() &&
		s.find(string(to_string(in[i][0]))+","+string(to_string(in[i][1]-1)))!=s.end()){
			int t=0;
			if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1]+1)))!=s.end())t++;
			if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1]-1)))!=s.end())t++;
			if(s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1]+1)))!=s.end())t++;
			if(s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1]-1)))!=s.end())t++;
			res[t]++;
		}
	}
	
	for(int i=0;i<5;i++){
		cout<<res[i]<<endl;
	}
	
	return 0;
}