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

## No comments:

## Post a Comment