PROGRAM Normes;
{
Epreuve informatique de l'Ecole Polytechnique           92.021
--------------------------------------------------------------

                    n
     Dans l'espace R  on définit classiquement la distance
     euclidienne de deux points M et M'  de coordonnées respec-
     tives  (x ) et (x' ) au moyen de la notation :
              i        i

                        n            2     1/2
            |MM'| = ( SOMME[ (x -x' )  ] )
                       i=1     i   i


1/   Soit A1, A2,....Ap   une famille fixe de p  points appar-
     tenant chacun à  Rn. Ecrire un programme Pascal qui calcu-
     le, en tout point M, de coordonnées (xi) la
     fonction M --> H(M)  définie par :

                      n            lambda
            H(M) =  SOMME[ (x -x' )       ]
                     i=1     i   i

     où lambda est un exposant fixé.


2/   Si M décrit une droite dans Rn, comment varie H(M) ?
     Illustrer cette variation par un graphe. Ecrire un pro-
     gramme qui cherche sur la droite un point M pour lequel
     H(M) atteint un extremum, et qui calcule ce dernier.

     Vérifier que dans le cas (n=2;lambda=2) on retrouve des
     résultats classiques de la géométrie plane.


3/   Si h est une constante réelle, quel est le lieu des
     points M tels que  H(M)=h ?

     Tracer cette courbe géométrique pour n=2; p=3.

     h restant toujours fixé, comment se déforme-t-elle en
     fonction de lambda ?


4/   Soit M° un point fixe distinct de chacun des Aj.
     Ecrire un programme Pascal capable de tracer le lieu des
     points M tels que H(M)=H(M°) pour un lambda fixé quelconque
     dans le cas du plan (n=2).

     Qu'observe-t-on lorsque :

      a)lambda-> infini?  b)lambda->+0 ?   c)lambda->-infini ?  d)lambda->-0?


                             -=-=-}

uses
  printer, crt, graph, modubase, entrees;


Const
     maxn = 30;
     maxp = 30;
     xmin = -1.5;
     xmax =  1.5;
     ymin = -1.2;


TYPE
    Point = vecteur;


VAR
     Ch         : Char ;
     n          : integer;      { Dimension de l'espace Rn   }
     p          : integer;      { Nombre de points Aj        }
     A          : array[1..maxp] of Point;
     M          : Point;
     M0,M1,M2   : Point;
     G          : Point;        { centre de gravité          }
     i,j        : Integer;

Function Distance(M1,M2:point):Real;
var
   v:real;
   i:byte;
begin
     v:=0;
     for i:=1 to n do
         v:=v+sqr(M1[i]-M2[i]);
     Distance := sqrt(v);
end;

Function H(M:Point;Lambda:real):real;
var
   v:real;
   j:byte;
begin
     v:=0;
     for j:=1 to p do
         v:=v+puissreal(Distance(M,A[j]),Lambda);
     H:=v ;
end;

Function Hpol(VAR M:Point;rho,theta,Lambda:real):real;
begin
     M[1]:=G[1]+rho*cos(theta);
     M[2]:=G[2]+rho*sin(theta);
     Hpol:=H(M,lambda);
end;

Procedure Cherche(VAR M:Point;z:real;t,lambda,eps:real);
var
   rho,rho1,rho2 : real;
   z0,z1,z2:real;
   u:integer;
begin
     rho1:=0;
     z1:=Hpol(M,rho1,t,Lambda)-z;
     rho2:=0;
     u:=0;
     repeat
     begin
           rho2:=rho2+1;
           u:=u+1;
           z2:=Hpol(M,rho2,t,Lambda)-z;
     end
     until (z1*z2<0) or (u>100);
     u:=0;
     if u<100 then
     repeat
     begin
          u:=u+1;
{          rho:=(z2*rho1-z1*rho2)/(z2-z1);    }
           rho:=0.5*(rho1+rho2)
          z0:=Hpol(M,rho,t,Lambda)-z;
          if z0*z1<0 then
             begin
                   rho2:=rho;
                   z2:=z0;
             end
          else
             begin
                   rho1:=rho;
                   z1:=z0;
             end;
     end
     until (abs(rho1-rho2)<eps) or (u>100);
end;

Procedure TirePoint(VAR M:Point);
var
   i:byte;
begin
     for i:=1 to n do
         M[i]:= 2*Random-1;
end;

Procedure MontrePoint(VAR M:Point);
var
   i:byte;
begin
     for i:=1 to n do
         Write('x[',i,']=',M[i]:8:5);
     Writeln;
end;

Procedure TracePoint(M:Point;nom:Char);
begin
     Croix(M[1],M[2]);
     Ecris(nom);
end ;

Procedure TraceTrait(M1,M2:Point);
begin
    Deplace(M1[1],M1[2]);
    Trace  (M2[1],M2[2]);
end;

Procedure DeplacePolaire(M:Point);
begin
    Deplace(M[1],M[2]);
end ;

Procedure TracePolaire(M:Point);
begin
    Trace(M[1],M[2]);
end ;





Procedure Interpole(VAR M:Point;M1,M2:Point;z:real);
begin
     M[1]:=M1[1]*z+M2[1]*(1-z);
     M[2]:=M1[2]*z+M2[2]*(1-z);
end;


Procedure TraceDroite(M1,M2:Point);
Var
   M:Point;
   z:Real;
begin
     z:=1;
     While z<100 do
           begi
                Interpole(M,M1,M2,z);
                TraceTrait(M,M1);
                TraceTrait(M,M2);
                z:=-z*2;
           end;
end;

Procedure Centre(VAR C:Point);
var
   i,j:byte;
begin
     For i:=1 to n do
     begin
           C[i]:=0;
           for j:=1 to p do
               C[i]:=C[i]+A[j,i];
           C[i]:=C[i]/p;
     end;
end;

Procedure Graphique;
var
   j:byte;
begin
     ModeGraphique;
     Efface;
     Isofenetre(xmin,xmax,ymin);
     Couleur(Brillant);
     TracePoint(G,'G');
     for j:=1 to p do
         TracePoint(A[j],Chr(Ord('A')+j-1));
end;





Procedure Presentation;
begin;
      Modetexte;
      Efface;
      WriteLN(' ====== Normes euclidiennes ============');
      WriteLN('                                        ');
      WriteLN('                                        ');
      WriteLN('   (1) Calcul de H(M)                   ');
      WriteLN('   (2) Extremum de H(M)                 ');
      WriteLN('   (3) Isogrammes de H(M)               ');
      WriteLN('   (4) Variation de Lambda              ');
      WriteLN('                              ');
      Write('   Tapez votre Choix  :  ');
end;




procedure Question1;
begin
     Graphique;
end;


Procedure Question2;
Var
     t,lambda:real;
     y:real;
Const
     tmin=-10;
     tmax= 10;
     hmin= -1;
     hmax= 10;
     pas =0.1;
     eps=0.01;
begin
     Graphique;
     Couleur(Brillant);
     TirePoint(M1);
     TirePoint(M2);
     Couleur(Vert);
     TraceDroite(M1,M2);
     Pause;
     Efface;
     Fenetre(tmin,tmax,hmin,hmax);
     Couleur(rouge);
     X_Axe(0,0,1);
     Y_Axe(0,0,1);
     Lambda:=-7;
     repeat
     begin
       lambda:=lambda+0.5;
       t:=tmin;
       Interpole(M,M1,M2,t);
       y:=H(M,lambda);
       Deplace(t,y);
       repeat
       begin
          t:=t+pas;
          Interpole(M,M1,M2,t);
          y:=H(M,Lambda);
          Trace(t,y);
          t:=t+pas;
     end
     until t>tmax;
   end
   until KeyPressed;
   Ch := ReadKey;
end;


Procedure Question3;
Var
     t,lambda:real;
     y:real;
Const
     pas =0.1;
     eps=0.01;
begin
   Graphique;
   Couleur(Vert);
   Lambda:=1/4;
   y:=3;
     repeat
     begin
       lambda:=lambda*2;
       Deplace(xmin,-ymin/2);
       Ecris('Lambda=');EcrisReel(Lambda);
       t:=0;
       Cherche(M,y,t,lambda,eps);
       DeplacePolaire(M);
       repeat
       begin
          t:=t+pas;
          Cherche(M,y,t,lambda,eps);
         { TracePoint(M,'M');}
          TracePolaire(M);
       end
       until t>2*pi;
    end
    until KeyPressed;
    Ch := ReadKey;
end;

Procedure TraceLambda(lambda0,Taux:real);
Var
     t:real;
     y:real;
     Lambda:real;
Const
     pas =0.1;
     eps=0.01;
begin
 repeat
 begin
   Graphique;
   TirePoint(M0);
   TracePoint(M0,'M');
   Lambda:=Lambda0;
   repeat
   begin
       Couleur(trunc(1+15*random));
       y:=H(M0,Lambda);
       Deplace(xmin,-ymin/2);
       Ecris('Lambda=');EcrisReel(Lambda);
       t:=0;
       Cherche(M,y,t,lambda,eps);
       DeplacePolaire(M);
       repeat
       begin
          t:=t+pas;
          Cherche(M,y,t,lambda,eps);
         { TracePoint(M,'M');}
          TracePolaire(M);
       end
       until t>2*pi;
       lambda:=lambda*Taux;
    end
    until KeyPressed;
    Ch := ReadKey;
 end
 until Ch=Chr(27);
end;



Procedure Question4;
begin
      Modetexte;
      Efface;
      WriteLN(' ====== Normes euclidiennes - Question 4 ===========');
      WriteLN('                                                         ');
      WriteLN('                                                         ');
      WriteLN('Si Lambda --> +Infini   on a à la limite :               ');
      WriteLN(' Max(MAj) = Max(M°Aj)                                    ');
      WriteLN(' C''est la frontière de l''intersection des p cercles      ');
      WriteLN(' centrés sur Aj et de rayon Max(M°Aj)                    ');
      WriteLN('                                                         ');
      WriteLN('Si Lambda --> -Infini   on a à la limite                 ');
      WriteLN(' Min(MAj) = Min(M°Aj)                                    ');
      WriteLN(' C''est la frontière de l''union des p cercles             ');
      WriteLN(' centrés sur Aj et de rayon Min(M°Aj)                    ');
      WriteLN('                                                         ');
      WriteLN('Si Lambda --> -0 ou +0  on a à la limite                 ');
      WriteLN(' MA1.MA2... MAp = M°A1.M°A2...M°Ap                       ');
      WriteLN(' C''est une sorte de cercle ou de patate                  ');
      WriteLN('                                                         ');
      WriteLN('                                        ');
      WriteLN('                                        ');
      WriteLN('                              ');
      Pause;
      Efface;
      WriteLN(' ====== Normes euclidiennes - Question 4 ===========');
      WriteLN('                                                         ');
      WriteLN('                                                         ');
      WriteLN('   (1) Lambda --> +Infini     ');
      WriteLN('   (2) Lambda --> +0          ');
      WriteLN('   (3) Lambda --> -Infini     ');
      WriteLN('   (4) Lambda --> -0          ');
      WriteLN('                              ');
      WriteLN('   (0) Terminer               ');
      WriteLN('                              ');
      WriteLN('   Tapez votre choix          ');
      WriteLN('                              ');

     Repeat
     begin
          Read(Ch);
     end
     until Ch in ['0'..'4'];
     case ch of
     '1':  TraceLambda(2,1.5);
     '2':  TraceLambda(2,0.5);
     '3' : TraceLambda(-2,1.5);
     '4' : TraceLambda(-2,0.5);
     '0' : Exit
     end;
     Pause;
end;

begin
     Efface;
     WriteLN(' ====== Normes euclidiennes ============');
   { WriteLN('                                        ');
     Write('Dimension de l''espace (n=2 conseillé) :');
     ReadLN(n);
     Write('Nombre de points Aj (p=3 conseillé) :');
     ReadLN(p); }
     n:=2;p:=3;
     Randomize;
     For j:=1 to p do
              TirePoint(A[j]);
     Centre(G);

     Pause;

     InitGraphique;
     while true do
     begin
          Presentation;
          Repeat
              Read(Ch)
          until Ch in ['0'..'4'];
          case ch of
               '1':  Question1;
               '2':  Question2;
               '3' : Question3;
               '4' : Question4;
               '0' : Halt
          end;
     Pause;
  end;
end.