Максимальная площадь, занятая треугольниками внутри правильного многоугольника
Задача звучит так:
Задается правильный n-угольник со стороной равной 1. Нужно найти максимальную площадь, занятую треугольниками, если вершины треугольников должны совпадать с вершинами многоугольника, но не пересекаться между собой (в том числе в вершинах).
Не особо понимаю, как к этой задаче подступиться
Ответы (4 шт):
Ну если не полной генерацией всего, что можно, то попробовать так:
Фиксируем первую вершину (ввиду симметрии), выбираем всеми способами (исключая симметричные уже имеющимся варианты) ещё две вершины первого треугольника, рекурсивно вызываем функцию для трёх (возможно пустых) оставшихся многоугольников, не включающих использованные вершины
AEJ взяли, решаем подзадачу для BCD (тут однозначно), FGHI, LK (вырожден):
Интересная получилась задачка... Вот первые решения — от 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;
}
}
}
Спустя 3 дня я сумел оптимизировать алгоритм (на nodejs) так чтобы он мог работать с большими n. Вот как выглядит распределение n > 20. Действительно, отношение стремиться к 1, многоугольник заполняется все большим количеством треугольников, а ширина полос уменьшается.
Но идея о том, что нужно выбирать рекуррентно самый большой треугольник не верна, так как в некоторых случаях, суммарная площадь получается не максимальной.
Например при n = 14, при таком подходе площадь совпадает с тем вариантом, когда мы перебираем все несимметричные варианты. А вот при n = 15, распределение треугольников другое и суммарная площадь оказывается ниже.
Очень интересно, как Вы получаете такие площади. Например, для десятиугольника по моим подсчётам на листочке и математическим формулам, я получил ответ с некоторой погрешностью от того, что мы должны получить (для удобства подсчёта разбил десятиугольник на части). На рисунке представляю Вам результаты, которые мы должны получить для n = 3, n = 10. Задание это из собеседования. 