时间：1s 空间：32M
题目描述：
1000 * 1000的网格上有n个大炮，大炮只会斜着45度开炮，方向不定。问你有多少对的大炮可以互相攻击到。
输入格式：
第一行输入一个整数n
接下来n行每行输入两个整数xi,yi，表示大炮的坐标
备注：同一个坐标可能有多个大炮
输出格式：
输出一个整数
样例输入：
5
1 1
1 5
3 3
5 1
5 5
样例输出：
6
约定：
1<=n<=200000,1<=xi,yi<=1000
错误代码：
#include<bits/stdc++.h>
using namespace std;
int cnt, x[100001], y[100001], n, i, j;
int main() {
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
for (j = 1; j <= n; j++) {
if (x[i] == x[j] || y[i] == y[j]) {
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
这么改，供参考：
#include <iostream>
//#include<bits/stdc++.h>
using namespace std;
int cnt, x[100001], y[100001], n, i, j;
int main() {
cin >> n;
for (i = 0; i < n; i++) {
cin >> x[i] >> y[i];
for (j = 0; j < i; j++) {
if (((x[i] - x[j]) * (x[i] - x[j])) == ((y[i] - y[j]) * (y[i] - y[j]))) {
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
思路：每输入一个大炮的坐标就进行判断
你的代码整个逻辑都是错的
正确的思路应该是判断每一条对角线，是否存在2个独立的坐标上都有大炮，如果有就累加这些大炮对
def count_attacking_pairs(n, cannons):
# 初始化字典，用于存储每个角度上的大炮数量
slope_count = {}
for i in range(n):
for j in range(i+1, n):
# 计算两个大炮的坐标差值
dx = cannons[i][0] - cannons[j][0]
dy = cannons[i][1] - cannons[j][1]
# 计算斜率，将斜率化简为分数形式
if dx == 0:
slope = float('inf')
else:
slope = dy / dx
if slope not in slope_count:
slope_count[slope] = 0
# 统计同一斜率上的大炮数目
slope_count[slope] += 1
# 计算可以互相攻击到的大炮对数
count = 0
for value in slope_count.values():
# 对于每个斜率上的大炮数目，可以组合出 C(value, 2) 对
count += value * (value - 1) // 2
return count
# 测试样例
cannons = [(1, 1), (1, 5), (3, 3), (5, 1), (5, 5)]
count = count_attacking_pairs(5, cannons)
print(count) # 输出 6
算法思路：
算法分析： 如果给定的大炮数量为n，则时间复杂度为O(n^2)，空间复杂度为O(n)。由于给定的数量范围较小，算法复杂度应该可以接受。