A school warm-up exercise to occupy your time - page 5

New comment
 
Aleksey Nikolayev:

1) It is difficult to prove the fact that the vertices of the maximal area must lie on the same circle (Cramer's theorem). I do not know how to prove it or where to read the proof.

2) I don't really believe in the existence of analytical formula for maximal area or radius of a circle.

3) The sum of array elements can be calculated by MathSum()

1) I think this is an obvious fact. And it is easy to prove by understanding that the maximal area of a triangle with a given vertex A, midline h and given opposite side a is the area of an isosceles triangle, when the angle at the given vertex is maximal. And the area of such triangle is h*a/2

Imagine that all nodes between given sides of polygons are flexible (like in a child's construction set on magnets) and it is clear that we can arrange the sides in such a way that all vertices have a common equidistant centre (provided that the larger side is smaller than the sum of other sides, otherwise they cannot be connected), i.e. they are inscribed in a circle. And this will be the maximum area, since it consists of the sum of the areas of isosceles triangles, with a side equal to the radius of this circle.

2) I believe

3) I did not find such formula in MQL4 or MQL5

 
Nikolai Semko:

1) I think this is an obvious fact.

intuitively yes, but it doesn't even stretch to a rigid proof by any stretch.

2) I believe

If there was one, it could be found, there is only a system of equations

Aleksey Nikolayev:

1) The difficulty is in proving the fact that the vertices of the mnc with the maximal area must lie on the same circle (Cramer's theorem). I don't know how to prove it or where to read the proof.

I did not find such a theorem at all, only references to this property.

Oleg avtomat:

http://algolist.ru/maths/geom/polygon/area.php

as always, useless links and no words on the point.

 
Andrei Trukhanovich:


as usual useless references and not a word of substance.

it's really useless to you

 
Nikolai Semko:

1) I think this is an obvious fact. And it is easily proved by understanding that the maximal area of a triangle with a given vertex A, midline h and given opposite side a is the area of an isosceles triangle when the angle at the given vertex is maximal. And the area of such triangle is h*a/2

Imagine that all nodes between given sides of polygons are flexible (like in a child's construction set on magnets) and it is clear that we can arrange the sides in such a way that all vertices have a common equidistant centre (provided that the larger side is smaller than the sum of other sides, otherwise they cannot be connected), i.e. inscribed in a circle. And this will be the maximum area, since it consists of the sum of the areas of isosceles triangles, with a side equal to the radius of this circle.

2) I believe

3) I haven't found such formula in MQL4 or MQL5.

1) Perhaps it can be somehow formalized as equality to zero of variation (derivative) of the area of a mnc by coordinates of vertices when they lie on one circle. Only this is a condition of local extremality and we need to prove 1) that it is a maximum and 2) that it is global.

3) MathSum()

#include <Math\Stat\Math.mqh>
void OnStart()
{
  double a[] = {1.0, 2.0, 3.0}, s;
  s = MathSum(a);
  Print("s=", s);
}

s=6.0



 

You get a polynomial from the roots of the other polynomials, and from all this baad over take three derivatives. Kilometric formulas. And who knows, maybe there's a surprise waiting at the end. We'll have to get some kind of trick.

 
Andrei Trukhanovich:

intuitively yes, but it doesn't even amount to a rigid proof by any stretch.

if there was one, it could be found, there is only a system of equations

I couldn't find such a theorem at all, only mentions of this property.

as usual useless references and not a single word on the point.

Googled "maximum area polygon given sides", found only that this result is "well known") and numerical solutions like the one given by Nikolay.

Apparently, you have to go through some ancient books on geometry - nowadays they don't like to expound on such things.

 

The above solution is only valid for polygons whose centre of the circumcircle lies inside the perimeter. Try triangle {2,2,3.9}

In general terms (approximation by precision double) the solution is as follows:

enum EEqual {LESS=-1,EQUALY,MORE};
//-------------------------------------------------------
struct SRes{
   double s;
   double r;
   double degDelta;
   SRes(){ZeroMemory(this);}
   SRes(double _s,double _r,double _degDelta):s(_s),r(_r),degDelta(_degDelta){}
   SRes(const SRes &other) {this=other;}
   bool operator !() {return !s;}
};
//-------------------------------------------------------
const double _2PI=2*M_PI;
//-------------------------------------------------------
EEqual Check(double &array[],int size){
   int ii=0;
   double max=0.0,
          tmp=0.0,
          sum=0.0;
   for (int i=0;i<size;++i){
      if (array[i]<=0.0) return false;
      max=MathMax(max,array[i]);
      if (max!=tmp){
         ii=i;
         tmp=max;}
      sum+=array[i];}
   EEqual ret=max<sum/2?MORE:LESS;
   if (ret==MORE){
      tmp=array[ii];
      array[ii]=array[--size];
      array[size]=tmp;}
   return ret;}
//---------------------------------------------------
SRes ComputeCenterOut(const double &array[], double deg){
   int size=ArraySize(array)-1;
   double r=array[size]/2.0/sin((deg-M_PI)/2.0);
   double sum=0.0,
          square=-r*cos(deg/2.0)*array[size]/2.0;
   for (int i=0;i<size;++i){
      double _deg=2.0*MathArcsin(array[i]/2.0/r);
      sum+=_deg;
      square+=r*cos(_deg/2.0)*array[i];}
   return SRes(square,r,deg-M_PI-sum);
}
//---------------------------------------------------
SRes ComputeCenterIn(const double &array[], double deg){
   int size=ArraySize(array)-1;
   double r=array[size]/2.0/sin(deg/2.0);
   double sum=deg,
          square=r*cos(deg/2.0)*array[size]/2.0;
   for (int i=0;i<size;++i){
      double _deg=2.0*MathArcsin(array[i]/2.0/r);
      sum+=_deg;
      square+=r*cos(_deg/2.0)*array[i]/2.0;}
   return SRes(square,r,_2PI-sum);
}
//---------------------------------------------------
SRes ComputeSquare(const double &array[],double min,double max,SRes &prev){
   double a=(min+max)/2.0;
   if (a==min||a==max) return prev;
   SRes res=a>M_PI?ComputeCenterOut(array,a):ComputeCenterIn(array,a);
   if (res.degDelta==0.0||res.s==prev.s) return res;
   if (res.degDelta>0.0) min=a;
   else max=a;
   return ComputeSquare(array,min,max,res);}
//---------------------------------------------------
SRes Square(const double &in[]){
   double tmp[];
   int size=ArrayCopy(tmp,in);
   if (Check(tmp,size)!=MORE) return SRes();
   double aMax=_2PI,
          a=aMax/size;
   return ComputeSquare(tmp,a,aMax,SRes());
}

void OnStart(void)
{
   double arr[]={2,3.9,2};
   ulong time=GetMicrosecondCount();
   SRes res=Square(arr);
   time=GetMicrosecondCount()-time;
   if (!res) Print("Многоугольника с заданными сторонами не существует");
   else PrintFormat("Time=%lli %ss\n"
                    "Square=%f\n"
                    "Radii=%f",time,"\xB5",res.s,res.r);
}
 
Vladimir Simakov:

The above solution is only valid for polygons whose centre of the circumcircle lies inside the perimeter. Try triangle {2,2,3.9}

...

What does this have to do with a triangle if the problem is to find a polygon with the maximum area given the dimensions of the sides?

 

Oops. I myself have only one of the variants counting correctly)))

UPD: Corrected.

 
Dmitry Fedoseev:

You get a polynomial from the roots of the other polynomials, and from all this baad over take three derivatives. Kilometric formulas. And who knows, maybe there's a surprise waiting at the end. We'll have to get some kind of trick.

Here's the function for the sum of all angles versus the radius. The solution area of 2p is highlighted in green.

Maybe this will help.
I'm too lazy to rack my brains, especially since I'm not very good at the tower.

Files:
Zadacha2.mq5  4 kb
12345678
New comment
Reason: