文章目录
0 效果1 题目2 思路3 代码
0 效果
难点：明白评分标准 数据结构的选用
1 题目
2 思路
首先明白的题目的评分是怎么评的。
评分标准为：当点(x,y)的
（
x
+
1
,
y
）
,
(
x
−
1
,
y
)
,
(
x
,
y
+
1
)
,
(
x
,
y
−
1
)
（x+1,y）,(x-1,y),(x,y+1),(x,y-1)
（x+1,y）,(x−1,y),(x,y+1),(x,y−1)都存在时，才开时评分，每当
(
x
+
1
,
y
+
1
)
,
(
x
+
1
,
y
−
1
)
,
(
x
−
1
,
y
+
1
)
,
(
x
−
1
,
y
−
1
)
(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)
(x+1,y+1),(x+1,y−1),(x−1,y+1),(x−1,y−1)【也就是四个角】存在一个评分加1分。
思路：
1 使用vector存储输入的点，使用map做hash表统计出现的点；2 对vector中存储的每个点检测
（
x
+
1
,
y
）
,
(
x
−
1
,
y
)
,
(
x
,
y
+
1
)
,
(
x
,
y
−
1
)
（x+1,y）,(x-1,y),(x,y+1),(x,y-1)
（x+1,y）,(x−1,y),(x,y+1),(x,y−1)是否存在，如果存在，则计算分数（每当
(
x
+
1
,
y
+
1
)
,
(
x
+
1
,
y
−
1
)
,
(
x
−
1
,
y
+
1
)
,
(
x
−
1
,
y
−
1
)
(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)
(x+1,y+1),(x+1,y−1),(x−1,y+1),(x−1,y−1)【也就是四个角】存在一个评分加1分），对计算后对应的分数的个数加1；3 输出每个分数段的点的个数 注意点：对于自定义数据结构的map，由于map的实现时红黑树（自平衡二叉查找树）构成，因此构建map时，需要分清左右子树，对于unordered_map来说，它是由散列表构成，自定义数据类型时，需要定义hash函数以及处理相同键值的碰撞情况。
3 代码
#include<cstdio>
#include<map>
#include<vector>
struct Data
{
int first
, second
;
Data(int _f
, int _s
):first(_f
),second(_s
){}
Data(){}
bool operator<(const Data
& a
) const
{
if(first
== a
.first
) return second
< a
.second
;
else return first
< a
.first
;
}
};
const int MAXN
= 1010;
std
::map
<Data
, int> pointHashTable
;
std
::vector
<Data
> point
;
int ans
[5] = {0};
int main(){
int n
, x
, y
;
scanf("%d", &n
);
while(n
--){
scanf("%d%d", &x
, &y
);
point
.push_back(Data(x
, y
));
pointHashTable
[Data(x
, y
)] = 1;
}
for(std
::vector
<Data
>::iterator i
= point
.begin();i
!= point
.end();i
++){
if(pointHashTable
[Data(i
->first
+ 1, i
->second
)] == 1
&& pointHashTable
[Data(i
->first
- 1, i
->second
)] == 1
&& pointHashTable
[Data(i
->first
, i
->second
+ 1)] == 1
&& pointHashTable
[Data(i
->first
, i
->second
- 1)] == 1){
int cnt
= 0;
if(pointHashTable
[Data(i
->first
+ 1, i
->second
+ 1)] == 1) cnt
++;
if(pointHashTable
[Data(i
->first
+ 1, i
->second
- 1)] == 1) cnt
++;
if(pointHashTable
[Data(i
->first
- 1, i
->second
+ 1)] == 1) cnt
++;
if(pointHashTable
[Data(i
->first
- 1, i
->second
- 1)] == 1) cnt
++;
ans
[cnt
]++;
}
}
for(int i
= 0;i
< 5;i
++){
if(i
!= 0) printf("\n");
printf("%d", ans
[i
]);
}
return 0;
}
