AcWing 3283. 回收站选址
原题链接
简单
(用一个集合来存数据,方便查找) $O(n*logn)$
只能用set,不能用unordered_set
C++ 代码
#include <iostream>
#include <set>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1},
dy[4] = {1, -1, 0, 0};
int ddx[4] = {1, 1, -1, -1},
ddy[4] = {-1, 1, 1, -1};
int cnt[5];
int n;
int main()
{
set<PII> h;
cin >> n;
while(n--)
{
int x, y;
cin >> x >> y;
PII p = {x, y};
h.insert(p);
}
for(auto c: h)
{
int t = 0;
for(int i = 0;i < 4; i++)
{
int a = c.x + dx[i], b = c.y + dy[i];
PII p = {a, b};
if(h.count(p)) t++;
}
if(t == 4)
{
int r = 0;
for(int i = 0;i < 4; i++)
{
int a = c.x + ddx[i], b = c.y + ddy[i];
PII p = {a, b};
if(h.count(p)) r++;
}
cnt[r]++;
}
}
for(int i = 0;i <= 4; i++)
cout << cnt[i] << endl;
return 0;
}