5

Задача звучит так:

Задается правильный n-угольник со стороной равной 1. Нужно найти максимальную площадь, занятую треугольниками, если вершины треугольников должны совпадать с вершинами многоугольника, но не пересекаться между собой (в том числе в вершинах).

Не особо понимаю, как к этой задаче подступиться

11
  • 1
    Так, как сформулировано - это по сути площадь n-угольника.
    – Harry
    5 дек 2022 в 6:54
  • @Harry, треугольники внутри многоугольника не должны иметь общих точек
    – Gl.k
    5 дек 2022 в 7:01
  • т.е. если полным перебором - генерируем все возможные триангуляции, в каждой выбираем подмножества несмежных треугольникиков, и ищем макс. суммарную площадь по всем подмножествам?
    – MBo
    5 дек 2022 в 7:02
  • @MBo, да, если полным перебором, то так
    – Gl.k
    5 дек 2022 в 7:04
  • 2
    @KovelPachnev Где вы увидели общие стороны и вершины? Учитываются закрашенные треугольники.
    – MBo
    6 дек 2022 в 17:18

4 ответа 4

7

Интересная получилась задачка... Вот первые решения — от 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;
        }
    }
}
9
  • У меня тоже по прикидкам получалось, что самый большой треугольник должен быть, никаких зебр, но я для малых n смотрел только. А вдруг там получится предела какой типа 1-1/e :)
    – MBo
    5 дек 2022 в 17:51
  • @MBo Я писал "на коленке", не сильно оптимизируя, так что считает для значений >15 довольно долго... Есть у меня подозрение, что при таки больших N появятся полосы третьего уровня, но и только, так что какой-то предел должен иметь место.
    – Harry
    5 дек 2022 в 17:59
  • @MBo Похоже, что предел будет равен 1 — стороны будут все меньше и меньше, просветы все уже и уже, так что будет практически все заполнено. Началось со 100% для треугольника, 100% же и закончится для ∞-угольника :)
    – Harry
    5 дек 2022 в 18:05
  • Предел - единица. Это можно доказать предъявив последовательности такого вида: берём центральный треугольник и три треугольника в основаниях горбушек. Остальные треугольники даже не строим. Для конструкции из четырёх треугольников доказываем что её предел (при росте n) - площадь шестиугольника. Добавляем ещё шесть треугольников, доказываем что её предел - площадь двенадцатиугольника. И так далее. Можно подобраться как угодно близко к площади 3 * 2^k-угольника. А их пощадь с ростом k стремиться к единице. 6 дек 2022 в 21:28
  • 1
    @StanislavVolodarskiy И стремится он к этому пределу примерно как 1/N (см. дополнение к ответу).
    – Harry
    9 дек 2022 в 18:57
5

Ну если не полной генерацией всего, что можно, то попробовать так:

Фиксируем первую вершину (ввиду симметрии), выбираем всеми способами (исключая симметричные уже имеющимся варианты) ещё две вершины первого треугольника, рекурсивно вызываем функцию для трёх (возможно пустых) оставшихся многоугольников, не включающих использованные вершины

AEJ взяли, решаем подзадачу для BCD (тут однозначно), FGHI, LK (вырожден):

введите сюда описание изображения

7
  • При этом следует не забывать, что у этих получившихся многоугольников уже часть вершин использовать нельзя...
    – Harry
    5 дек 2022 в 7:18
  • 1
    @Harry, это просто. Скорее всего алгоритм будет такой: выбрать самой большой треугольник (у него интервалы в индексах примерно равны) в правильном многоугольнике. От каждой стороны отступить. В оставшихся горбушках построить наибольшие треугольники на основаниях горбушек (примерное равенство интервалов тут тоже важно). Повторить рекурсивно. 5 дек 2022 в 8:00
  • А как считать площади для полученных треугольников?
    – Gl.k
    5 дек 2022 в 8:18
  • @grrrrrred Вы серьёзно? ru.stackoverflow.com/a/1104633/291659 area разделить на два
    – MBo
    5 дек 2022 в 8:22
  • 1
    @SpaceResearcher. Geogebra
    – MBo
    8 дек 2022 в 10:35
5

Спустя 3 дня я сумел оптимизировать алгоритм (на nodejs) так чтобы он мог работать с большими n. Вот как выглядит распределение n > 20. Действительно, отношение стремиться к 1, многоугольник заполняется все большим количеством треугольников, а ширина полос уменьшается.

n > 20 n > 170

Но идея о том, что нужно выбирать рекуррентно самый большой треугольник не верна, так как в некоторых случаях, суммарная площадь получается не максимальной.

Например при n = 14, при таком подходе площадь совпадает с тем вариантом, когда мы перебираем все несимметричные варианты. А вот при n = 15, распределение треугольников другое и суммарная площадь оказывается ниже.

введите сюда описание изображения

4
  • Отличное исследование! 7 дек 2022 в 8:29
  • "идея о том, что нужно выбирать рекуррентно самый большой треугольник не верна" — а разве в предыдущих ответах где-то об этом говорилось?
    – Mikhailo
    7 дек 2022 в 9:31
  • 1
    Интересно, а как вы оптимизировали, что для сотен считаете?
    – Mikhailo
    7 дек 2022 в 9:38
  • @ArtemKochetkov. Для начала нужно, получить массив из координат вершин многоугольника, так как это правильный n-угольник, то это сделать просто, затем имея 3 координаты, можно посчитать площадь треугольника, длину стороны знать не обязательно.
    – amoonra
    8 дек 2022 в 17:25
2

Очень интересно, как Вы получаете такие площади. Например, для десятиугольника по моим подсчётам на листочке и математическим формулам, я получил ответ с некоторой погрешностью от того, что мы должны получить (для удобства подсчёта разбил десятиугольник на части). На рисунке представляю Вам результаты, которые мы должны получить для n = 3, n = 10. Задание это из собеседования. введите сюда описание изображения

3
  • Для n = 3 получится равносторонний треугольник. Далее по формуле: p = (a + b + c)/2 = 1/2*(1 + 1 + 1) = 1.5 Ну, а дальше - S = √p(p - a)(p - b)(p - c) = = √(1.5)(1.5 - 1)(1.5 - 1)(1.5 - 1) = = √(1.5)·(0.5)·(0.5)·(0.5) = √0.1875 = √3/4 ≈ 0.4330127018922193 (м)2 Ну или по двум сторонам и углу между ними 1/2· 1 · 1 ·sin 60° = 0.25√3 (м)2 ≈ 0.4330127018922193 (м)2 8 дек 2022 в 8:23
  • У Harry использована окружность r=1, у Ивана дано отношение к площади круга. То, что не использовано со стороной равной 1 - мелочь
    – MBo
    8 дек 2022 в 8:35
  • @MBo теперь понял, спасибо. 8 дек 2022 в 9:45

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.