Интересная получилась задачка... Вот первые решения — от 3 до 20 и соответственно графики. Числа внутри картинок — площадь покрытия и ее отношение к площади многоугольника (на графике соответственно синяя и красная линия). Если кто какую математику сумеет привязать и рассказать, было бы интересно посмотреть...


Update 1
На 25-угольнике проклюнулся подтверждающий идею пятый треугольник:

Переписал с применением ДП, скорости достаточно, чтоб просчитывать сотни... На картинках уже ничего не разглядеть, но при N=282 (пятый порядок треугольников) площадь треугольников 93.6% от площади многоугольника.
Update 2
Ну, и последняя капля :) Пусть
- площадь N-угольника, а
- площадь покрытия треугольниками.
По моим прикидкам, при больших N (ну, там, тысячи хотя бы...)

Update 3
По просьбам на e-mail и в комментариях. Вот две программки, писано на бегу, когда вечером свет есть, так что качество — какое уж есть. Все компилил VC++2019.
Получение оптимального решения для N-угольника.
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <numbers>
#include <array>
#include <map>
using namespace std;
struct Pnt
{
double x,y;
};
Pnt pnt(int i, int N)
{
Pnt p;
p.x = cos(2*numbers::pi*i/N);
p.y = sin(2*numbers::pi*i/N);
return p;
}
using Trigon = array<int,3>;
using Soltri = vector<Trigon>;
struct Solution
{
int N, count;
double S = -1;
Soltri sol;
};
// pair<int,int> - N и количество вершин (отсчет c 0)
map<pair<int,int>,Solution> Rep;
// Площадь треугольника
double Area(int i, int j, int k, int N)
{
return abs(sin(2*numbers::pi*(j-i)/N) + sin(2*numbers::pi*(k-j)/N) + sin(2*numbers::pi*(i-k)/N))/2;
}
// pair<int,int> - начальная вершина и их количество
double S(pair<int,int> d, Soltri& st, int N)
{
if (d.second < 3) return 0;
if (auto sl = Rep.find(make_pair(N,d.second)); sl != Rep.end())
{
for(auto t: sl->second.sol)
{
t[0] += d.first;
t[1] += d.first;
t[2] += d.first;
st.push_back(t);
}
return sl->second.S;
}
double maxS = 0;
Soltri trs;
for(int i = d.first; i < d.first + d.second - 2; ++i)
for(int j = i+1; j < d.first + d.second - 1; ++j)
for(int k = j+1; k < d.first + d.second; ++k)
{
Soltri cur;
Trigon t {i,j,k};
cur.push_back(t);
double pS = Area(i,j,k,N);
pair<int,int> a[4];
a[0] = make_pair(d.first,i - d.first);
a[1] = make_pair(i+1,j - i - 1);
a[2] = make_pair(j+1,k - j - 1);
a[3] = make_pair(k+1,d.second - k - 1);
pS += S(a[0],cur,N) + S(a[1],cur,N) + S(a[2],cur,N) + S(a[3],cur,N);
if (pS > maxS)
{
maxS = pS;
trs = cur;
}
}
Solution sol;
sol.N = N; sol.count = d.second; sol.S = maxS;
for(auto m: trs)
{
st.push_back(m);
for(int& tg: m) tg -= d.first;
sol.sol.push_back(m);
}
Rep.insert(make_pair(make_pair(N,d.second),sol));
return maxS;
}
double Sol(Soltri& st, int N)
{
double maxS = 0;
Soltri trs;
int i = 0;
for(int j = 1; j < N - 1; ++j)
for(int k = j+1; k < N; ++k)
{
Soltri cur;
Trigon t{i,j,k};
cur.push_back(t);
double pS = Area(i,j,k,N);
pair<int,int> a[4];
a[0] = make_pair(i+1,j - i - 1);
a[1] = make_pair(j+1,k - j - 1);
a[2] = make_pair(k+1,N - k - 1);
pS += S(a[0],cur,N) + S(a[1],cur,N) + S(a[2],cur,N);
if (pS > maxS)
{
maxS = pS;
trs = cur;
}
}
for(auto m: trs) st.push_back(m);
return maxS;
}
double S(int N, Soltri& sol)
{
sol.clear();
return Sol(sol,N);
}
double Sn(int N)
{
return N*sin(2*numbers::pi/N)/2;
}
int main(int argc, char * argv[])
{
cout << fixed << setprecision(6);
for(int N = 5; N < 50; ++N )
{
Soltri sol;
double s = S(N,sol);
cout << setw(2) << N << ": "
<< setw(10) << s
<< setw(10) << s/Sn(N) << endl;
for(auto t: sol)
{
for(auto p: t) cout << p << " ";
cout << endl;
}
}
}
Расчет (не)покрытой площади для N=9*2^k-6
#include <iostream>
#include <iomanip>
#include <cmath>
#include <numbers>
using namespace std;
double Sn(int N)
{
return N*sin(2*numbers::pi/N)/2;
}
double Area(int i, int j, int k, int N)
{
return abs(sin(2*numbers::pi*(j-i)/N) + sin(2*numbers::pi*(k-j)/N) + sin(2*numbers::pi*(i-k)/N))/2;
}
int main()
{
for(int k = 1; k < 21; ++k)
{
int N = (1 << k)*9-6;
double s = 0;
int L = 1;
for(int i = k-1; i >= 0; --i)
{
int count = 3*(1<<i);
s += count *Area(0,L,2*L,N);
L = L*2 + 2;
}
s += Area(0,L,2*L,N);
s = s/Sn(N);
cout << N << " " << setprecision(15) << 1.0-s << endl;
}
}
Update 4
Все, проломил односекундный барьер для 500 :)
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <numbers>
#include <array>
#include <map>
using namespace std;
struct Pnt
{
double x,y;
};
Pnt pnt(int i, int N)
{
Pnt p;
p.x = cos(2*numbers::pi*i/N);
p.y = sin(2*numbers::pi*i/N);
return p;
}
using Trigon = array<int,3>;
using Soltri = vector<Trigon>;
struct Solution
{
int N, count;
double S = -1;
Soltri sol;
};
// pair<int,int> - N и количество вершин (отсчет c 0)
map<pair<int,int>,Solution> Rep;
// Площадь треугольника
double Area(int i, int j, int k, int N)
{
return abs(sin(2*numbers::pi*(j-i)/N) + sin(2*numbers::pi*(k-j)/N) + sin(2*numbers::pi*(i-k)/N))/2;
}
// pair<int,int> - начальная вершина и их количество
double S(pair<int,int> d, Soltri& st, int N)
{
if (d.second < 3) return 0;
if (auto sl = Rep.find(make_pair(N,d.second)); sl != Rep.end())
{
for(auto t: sl->second.sol)
{
t[0] += d.first;
t[1] += d.first;
t[2] += d.first;
st.push_back(t);
}
return sl->second.S;
}
double maxS = 0;
Soltri trs;
int i = d.first, k = d.first + d.second-1;
for(int j = max((i+k)/2,i+1); j < min((i+k)/2+3,k); ++j)
{
Soltri cur;
Trigon t {i,j,k};
cur.push_back(t);
double pS = Area(i,j,k,N);
pair<int,int> a[4];
a[0] = make_pair(d.first,i - d.first);
a[1] = make_pair(i+1,j - i - 1);
a[2] = make_pair(j+1,k - j - 1);
a[3] = make_pair(k+1,d.second - k - 1);
pS += S(a[0],cur,N) + S(a[1],cur,N) + S(a[2],cur,N) + S(a[3],cur,N);
if (pS > maxS)
{
maxS = pS;
trs = cur;
}
}
Solution sol;
sol.N = N; sol.count = d.second; sol.S = maxS;
for(auto m: trs)
{
st.push_back(m);
for(int& tg: m) tg -= d.first;
sol.sol.push_back(m);
}
Rep.insert(make_pair(make_pair(N,d.second),sol));
return maxS;
}
double Sol(Soltri& st, int N)
{
double maxS = 0;
Soltri trs;
int i = 0;
for(int j = max(N/3 - 2,1); j < max(N/3+2,N); ++j)
for(int k = max(2*N/3 - 2,j+1); k < max(2*N/3+2,N); ++k)
{
Soltri cur;
Trigon t{i,j,k};
cur.push_back(t);
double pS = Area(i,j,k,N);
pair<int,int> a[4];
a[0] = make_pair(i+1,j - i - 1);
a[1] = make_pair(j+1,k - j - 1);
a[2] = make_pair(k+1,N - k - 1);
pS += S(a[0],cur,N) + S(a[1],cur,N) + S(a[2],cur,N);
if (pS > maxS)
{
maxS = pS;
trs = cur;
}
}
for(auto m: trs) st.push_back(m);
return maxS;
}
double S(int N, Soltri& sol)
{
sol.clear();
return Sol(sol,N);
}
double Sn(int N)
{
return N*sin(2*numbers::pi/N)/2;
}
int main(int argc, char * argv[])
{
cout << fixed << setprecision(6);
for(int N: {250,500})
{
Soltri sol;
double s = S(N,sol);
cout << setw(2) << N << ": "
<< setw(10) << s
<< setw(10) << s/Sn(N) << endl;
for(auto t: sol)
{
for(auto p: t) cout << p << " ";
cout << endl;
}
}
}