n = int(input()) row = [0]*(n+1) col = [0]*(n+1) slash1 = [0]*(2*n) slash2 = [0]*(2*n) for _ in range(n): x, y = map(int, input().split()) row[x] += 1 col[y] += 1 slash1[x-y+(n-1)] += 1 slash2[x+y-(n-1)] += 1 res = 0 for i in range(1, n+1): res += (row[i]*(row[i]-1))//2 res += (col[i]*(col[i]-1))//2 for i in range(1, 2*n): res += (slash1[i]*(slash1[i]-1))//2 res += (slash2[i]*(slash2[i]-1))//2 print(res)
用模拟的话复杂度O(n^2),但是把每一行、列、斜线的棋子个数存下来用组合数公式遍历相加复杂度就是O(n)了。
注意数据类型用long long不要用int
别忘了还有副对角线[捂脸]
组合数直接用公式求,求的过程中记得保证乘数是long long类型,否则结果会溢出
一个方向对角线有2n - 1条,需要构建好坐标到对角线的映射
用模拟的话复杂度O(n^2),但是把每一行、列、斜线的棋子个数存下来用组合数公式遍历相加复杂度就是O(n)了。
注意数据类型用long long不要用int
别忘了还有副对角线[捂脸]
组合数直接用公式求,求的过程中记得保证乘数是long long类型,否则结果会溢出
一个方向对角线有2n - 1条,需要构建好坐标到对角线的映射