题目：https://ac.nowcoder.com/acm/problem/15295
思路：
结构体的id用来记录这个点，不然排序会把点的顺序打乱
排四个序，分别代表上下，左右，正对角线，副对角线
注意排序时遇到相等的，要根据其他坐标来排，例如x相同时，y最小的威胁只有右边，y最大的威胁只有左边，两人端点时只加了一次的
每排一遍序就要扫一遍
例如q[ i ].x==q[i-1].x
cnt[ q[ i ].id ]++; 是指这个点左边有威胁
cnt[ q[ i-1 ].id ]++; 是指这个点右边有威胁
最后从1-m遍历一次，统计次数
//换位思考从各个方向来遍历点 //当一个方向行不通，学会逆向思考 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=1e5+7; int n,m; int cnt[maxn]={0}; int num[10]={0}; struct qi { int x,y,id; }; struct qi q[maxn]; int cmp1(qi a,qi b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cmp2(qi a,qi b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } int cmp3(qi a,qi b) { if(a.x-a.y==b.x-b.y) return a.x<b.x; return a.x-a.y<b.x-b.y; } int cmp4(qi a,qi b) {if(a.x+a.y==b.x+b.y) return a.x<b.x; return a.x+a.y<b.x+b.y; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d",&q[i].x,&q[i].y); q[i].id=i; } sort(q+1,q+m+1,cmp1); for(int i=2;i<=m;i++) { if(q[i].x==q[i-1].x) { cnt[q[i].id]++; cnt[q[i-1].id]++; } } sort(q+1,q+m+1,cmp2); for(int i=2;i<=m;i++) { if(q[i].y==q[i-1].y) { cnt[q[i].id]++; cnt[q[i-1].id]++; } } sort(q+1,q+m+1,cmp3); for(int i=2;i<=m;i++) { if(q[i].x-q[i].y==q[i-1].x-q[i-1].y) { cnt[q[i].id]++; cnt[q[i-1].id]++; } } sort(q+1,q+m+1,cmp4); for(int i=2;i<=m;i++) { if(q[i].x+q[i].y==q[i-1].x+q[i-1].y) { cnt[q[i].id]++; cnt[q[i-1].id]++; } } for(int i=1;i<=m;i++) { num[cnt[q[i].id]]++; } for(int i=0;i<8;i++) printf("%d ",num[i]); printf("%d\n",num[8]); }
原文：https://www.cnblogs.com/aacm/p/14864175.html