Hello, Codeforces. Recently I invented a problem. Consider a set of points (x, y) with integer coordinates, 0 <= x < a и 0 <= y < b. We want to know the number of acute triangles with vertices at given points.
Trying to interpolate
We can write function f(a, b) which finds the answer and works in (ab) ^ 3. I suggested that it is a polynomial of two variables with degree <= 6. I tried to interpolate it using this theorem. But my code finds non-zero coefficients with monoms with degrees > 6, so my hypothesis was not confirmed. I also failed with right triangles.
This code finds a coefficient with a ^ (C1 - 1) * b ^ (C2 - 1)
What I would like to know:
- can this problem be solved faster than O(stupid(a, b))
- can this problem be solved in O(1)
- maybe, someone knows problems with difficult to find formulas and this method can help to find them?
UPD: Found formula for the number of right triangles with b = 2: f(a, 2) = 2 * a ^ 2 - 4, a > 1.
UPD2: Many thanks to bronze_coder for finding O(1) solution for constant b: OEIS A189814.
Interpolation should use ai > b ^ 2.
UPD3: Finally wrote a O((ab) ^ 2) solution.
Now I can interpolate using bigger values of a and b.
But it is quite strange for me that the number of right triangles is directly proportional to (ab) ^ 2 instead of (ab) ^ 3. Now I will try to understand why the formula doesn't work with ai <= b ^ 2.
UPD4: Code that finds a formula for f(a, b) for a > b ^ 2 and works in O(b ^ 6):
