Рассмотрим множество точек **_(x, y)_** с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.↵
↵
### Попытки проинтерполировать↵
Ясно, что можно написать функцию **_f(a, b)_**, которая будет искать ответ и работать при этом за `(ab) ^ 3`. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя [эту теорему
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](https://
Не получилось также с тупоугольными и прямоугольными треугольниками.↵
↵
<spoiler summary="code (для прямоугольных треугольников
I also failed with right triangles.↵
↵
<spoiler summary="code (for right triangles)">↵
~~~~~↵
int stupid(int a, int b)↵
{↵
int ans = 0;↵
for (int x1=0;x1<a;x1++)↵
for (int x2=0;x2<a;x2++)↵
for (int x3=0;x3<a;x3++)↵
for (int y1=0;y1<b;y1++)↵
for (int y2=0;y2<b;y2++)↵
for (int y3=0;y3<b;y3++)↵
{↵
int a = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);↵
int b = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);↵
int c = (x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2);↵
if ((a + b == c) && min(a, min(b, c))) ans++;↵
} ↵
return ans / 2;↵
}↵
signed main()↵
{↵
int C1 = 5, C2 = 5;↵
ld res = 0;↵
for (int a1=4;a1<=C1+3;a1++)↵
{↵
for (int a2=4;a2<=C2+3;a2++)↵
{↵
int d = 1;↵
for (int ai=4;ai<=C1+3;ai++) if (ai != a1) d *= a1 - ai;↵
for (int ai=4;ai<=C2+3;ai++) if (ai != a2) d *= a2 - ai;↵
res += (ld)(stupid(a1, a2)) / d;↵
}↵
}↵
cout << setprecision(20) << fixed << res;↵
}↵
~~~~~↵
</spoiler>↵
↵
### Что я хотел бы узнать:↵
- решается ли эта задача быстрее, чем за куб↵
- решается ли эта задача за O(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?
