1334: PIPI计数
题目描述
在二维平面上分布着一些坐标点，PIPI想知道每个坐标点上下左右有多少个坐标点与它相邻，请你帮PIPI算一下。
输入
输入第一行包含一个正整数 n (n<=1e5),代表坐标点的个数。
接下来n行，每行输入一个坐标点的坐标 x, y( -1e9<=x,y<=1e9 )
输出
输出一共n行，对于每个坐标点，输出与其相邻的坐标点的个数。
样例输入
4
1 1
0 1
1 0
1 2
样例输出
3
1
1
1
思路
此题有个坑，即坐标（x，y）为整数且同一个坐标可以有多个点，题中没有明确说明。最直观的解法是用二维数组模拟一个二维坐标系，然而 -1e9<=x, y<=1e9，显然 c++ 不允许我们使用这么大的内存空间，故要想到使用 map 容器存储题目中输入的点，然后再检索其上下左右四个方向是否存在邻接点。
#include<bits/stdc++.h>
using namespace std;
int main()
{int n, x[100010], y[100100];scanf("%d", &n);map<pair<int, int>, int> mp;for(int i = 0; i < n; i++){scanf("%d%d", &x[i], &y[i]);mp[{x[i], y[i]}]++;}for(int i = 0; i < n; i++){int ans = 0;ans += mp[{x[i] - 1, y[i]}];ans += mp[{x[i] + 1, y[i]}];ans += mp[{x[i], y[i] - 1}];ans += mp[{x[i], y[i] + 1}];printf("%d\n", ans);}return 0;
}