A fast way to find out whether two elements in matrix share the same diagonal

Let's have the following matrix:

     1 2 3 4 5
     -----------
1 | 0 0 0 0 0
2 | 0 0 1 0 0
3 | 0 0 0 0 0
4 | 1 0 0 0 0
5 | 0 0 0 0 0

with two points: (x1, y1) = (2, 3) and (x2, y2) = (4, 1).

The fastest way to find out whether these two points share the same diagonal is the result of this expression:

bool result = (x1 + y1 == x2 + y2) or (x1 - y1 == x2 - y2)

Now let's complicate the task. Given matrix n x n with m points, find the minimum number of diagonals which contain at least two points. The first line of the input contains: n m. The next m lines contain points with coordinates (xi, yi).

Example:

     1 2 3 4 5
    ------------
1 | 1 0 0 0 1
2 | 0 0 0 0 0
3 | 1 0 1 0 0
4 | 0 0 0 0 0
5 | 1 0 1 0 0

Input:
5 6
1 1
1 5
3 1
3 3
5 1
5 3

Output:
3

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <unordered_map> using namespace std; int main() { int m; cin >> m; unordered_map<int, int> cntAdd; unordered_map<int, int> cntSub; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; cntAdd[x + y]++; cntSub[x - y]++; } int result = 0; for (auto& cnt : cntAdd) if (cnt.second > 1) result++; for (auto& cnt : cntSub) if (cnt.second > 1) result++; cout << result << endl; return 0; }

Here's a good problem for practicing: http://codeforces.com/contest/621/problem/B