VOJ - CT

Source: CT
Tags: Maths - Geometry

Problem:
Cho một lưới tọa độ 2D có góc trái dưới (0, 0) và góc phải trên (X, Y). C truy vấn, đếm số lượng tam giác vuông cân có 3 đỉnh là các điểm trên lưới (tọa độ nguyên).
C ≤ 20. 0 ≤ X, Y ≤ 1e3.

Ví dụ:
Input:
2
0 3
1 1

Output:
0
4

Explanation:
Tự vẽ hình đếm đi :D

Solution:
Gọi (x1, y1) là một điểm trên lưới, coi điểm này là đỉnh vuông cân của tam giác, với một điểm (x2, y2) khác bất kỳ, ta có thể tìm được điểm (x3, y3) tương ứng là (x1 ± (y1 - y2), y1 ± (x1 - x2)).

Vậy vấn đề duy nhất đó là cần xác định cặp điểm nào có (x3, y3) vẫn nằm trên lưới. Nếu liệt kê ra tất cả các cặp điểm thì rõ ràng là không ổn chút nào (khoảng O(X^2 * Y^2)), nên ta sẽ cố định một điểm (x1, y1) rồi xác định xem vùng nào chứa những điểm (x2, y2) mà tìm được điểm (x3, y3) tương ứng vẫn nằm trên lưới.
Gọi (i, j) thay cho (x1, y1) (để dễ nhìn với cả type đỡ mỏi tay :">), chia lưới thành 4 vùng theo đường cắt dọc và ngang.

Nhận thấy rằng, những điểm trong một vùng được chọn sẽ tìm được điểm tương ứng trong vùng kề. Tất nhiên là một điểm trong vùng 1 tìm thấy tương ứng ở vùng 2 và ngược lại là như nhau, vì vậy ta sẽ chỉ xét những điểm ở một vùng mà tìm được điểm tương ứng ở vùng kề theo chiều kim đồng hồ để không bị xét trùng. Gọi a1 là độ dài theo x của vùng 1, b1 là độ dài theo y của vùng 1, tương tự a2, b2, a3, b3, và a4, b4.

Xét vùng 1, ta có x3 = x1 + y1 - y2 = i - b1 và y3 = y1 + x1 - x2 = j + a1, và vì ta muốn điểm tương ứng này vẫn phải nằm trong vùng 2, do đó x3 = i - min(b1, a2) và y3 = j + min(a1, b2).

Vùng màu xanh lá là vùng chứa những điểm (x2, y2) có thể chọn

Khi đã xác định được vùng những điểm có thể chọn rồi thì công thức tính rất đơn giản (gọi n, m là độ dài các cạnh của vùng): (n + 1) * (m + 1) - 1. Nhưng để ý một chút, những điểm nằm ở cạnh dọc bên phải của vùng sẽ bị tính lại một lần nữa khi xét vùng 2 và 4, do đó ta phải rút lại vùng có thể chọn mới như sau

Vậy công thức giờ là (n + 1) * m.
Tính tương tự lần lượt các vùng còn lại, ta sẽ có kết quả.
Độ phức tạp O((X + 1) * (Y + 1))

Code:
#include <iostream>

using namespace std;

int main() {
    int q; cin >> q;
    for (int x, y; q--;) {
        cin >> x >> y;
        long long res = 0;
        for (int i = 0; i <= x; i++)
            for (int j = 0; j <= y; j++)
                res += (min(j, i) + 1) * min(i, y - j),                res += (min(i, y - j) + 1) * min(y - j, x - i),
                res += (min(y - j, x - i) + 1) * min(x - i, j),
                res += (min(x - i, j) + 1) * min(j, i);
        cout << res << '\n';
    }

}