1000*1000的格子里,给你n≤200 000个点的坐标,求有多少对在一个对角线上。
考虑到对角线总共就主对角线1999条+副对角线1999条,我们可以求每个对角线有几对点。
同一条主对角线上的元素有a[i]个,就有C(a[i],2)对点;
同一条副对角线上的元素有b[i]个,就有C(b[i],2)对点。
读入x和y后,
x+y相同的就在同一副对角线,x+y范围是(2,2000),
x-y相同的就是同一主对角线,x-y范围是(-999,999),加上1001就是(2,2000)了
x+y==2和2000的对角线只有一个元素,x-y+1000==2和2000的只有一个元素,所以只要求x+y==2到1998,和x-y+1001==2到1998的对角线。
这样就可以每次计算a[i]和b[i]的对角线有几对点,i=2到1998
#include <stdio.h>
#define N 2005
long long n,x,y,a[N],b[N],ans;
int main()
{
scanf("%I64d",&n);
for(int i=1; i<=n; i++)
{
scanf("%I64d%I64d",&x,&y);
a[x-y+1001]++;
b[x+y]++;
}
for(int i=2; i<=1998; i++)ans+=a[i]*(a[i]-1)/2+b[i]*(b[i]-1)/2;
printf("%I64d",ans);
return 0;
}