CCF认证 2019-12-3

woxiaosade 2021-12-08 原文

分析

后面的数据，坐标分布太离散，不能用一个二位数组来模拟垃圾分布。因此，考虑用一个数组记录每个垃圾点的位置。

先根据x坐标、再根据y坐标进行排序。
再遍历数组中的每一处垃圾点，判断其是否能建回收站(相邻处有无垃圾)，在判断对角线的垃圾点数目
判断的过程中，可以用二分查找减少查找时间，毕竟已经排好序了。

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
class pos{
public:
	int x, y;
	
	pos(){
		
	}
	pos(int _x, int _y){
		x = _x;
		y = _y;
	}
	bool operator==(const pos a){
		if(a.x == x && a.y == y)	return true;
		else return false;
	}
	
	bool operator<(const pos a) const{
		if(x < a.x)
			return true;
		else if(x == a.x){
		if(y < a.y)
			return true;
		else
			return false;
		}
		else
			return false;
	}
	
};


int n;
pos a[1002];
int num[5];
int dir1[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dir2[4][2] = {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

int main(){
	cin >> n;
	int x = 0, y = 0;
	for(int i = 0;i < n; i++){
		scanf("%d %d", &x, &y);
		a[i] = pos(x, y);
	}
	sort(a, a + n);
	
	for(int i = 0; i < n; i++){
		int flag = 0;
		for(int j = 0; j < 4;j++){
			flag += binary_search(a, a + n, pos(a[i].x + dir1[j][0], a[i].y + dir1[j][1]));
		}
		
		if(flag ==  4){
			flag = 0;
			for(int j = 0; j < 4;j++){
				flag += binary_search(a, a + n, pos(a[i].x + dir2[j][0], a[i].y + dir2[j][1]));
			}
			num[flag]++;
		}
		
	}
	
	for(int i = 0;i < 5; i++){
		cout << num[i] << endl;
	}
	return 0;
}