PROGRAM ep96_402;

{
	Epreuve informatique de l'Ecole Polytechnique 96.402

Dans un espace Rn euclidien de dimension n, on se donne une famille
A1, A2 ... Ak de k points fixes.

On associe … tout point M de Rn la quantit‚  
 f(M)=sup(MAi)

o— MAi d‚signe la distance euclidienne du point M au point Ai,
et sup est la plus grande des distances obtenues.

1/ Ecrire un programme Pascal qui calcule la fonction scalaire f(M)
pour tout point M d‚fini par ses coordonn‚es r‚elles  (x1, x2, .... xn),
et qui montre comment varie f(M) lorsque M se d‚place selon une
droite D passant par deux points fixes quelconques P et Q.

2/ Montrer que la fonction f(M) atteint un minimum en un point M0
n‚cessairement unique. Ecrire un programme qui recherche ce minimum.

3/ Dans le cas o— n=2 tracer le lieu du point M tel que f(M)=C
pour diff‚rentes valeurs de la constante C. Que remarque-t-on ?

4/ Comment peut on traiter le cas o— la famille Ai contient une
infinit‚ d'‚l‚ments ?
Montrer que s'il existe un majorant de la distance OAi o— O est un
point fixe arbitrairement choisi dans Rn, il existe encore dans ce cas
une solution M0. 

    * * *

Applications num‚riques sugg‚r‚es  : 

- pour les questions 1 … 3 :
	les n coordonn‚es xj du point Ai   sont donn‚es par la formule
        x[j]=i*cos(j+h)  o— h est une constante.

- pour la question 4

	dans un plan euclidien, ensemble de points A dont les coordonn‚es
        sont r.cos(t), r.sin(t) avec
	r.t=r0.t0  t>t0  (o— r0 et t0  sont deux constantes positives)

:--------------------------------------------------------------:
:    Imprimer tous les r‚sultats                               :
:     en indiquant chaque fois … quoi ils correspondent        :
:--------------------------------------------------------------:
                            -=-=-=-

	
}


uses
  crt,modubase;

const
   maxpoints=99;
   maxn=3;

type
    MyReal=real;
    Longueur=MyReal;
    Area=MyReal;
    Coordinates=array[1..maxn] of Longueur;
    Points = record
                  x:Coordinates;
                  t:string;
    end;
    Vecteurs =Coordinates;

var
   A:array[0..maxpoints] of Points;
   O:Points;
   n,k,isup:integer;
   ch:char;
   Car         : Char ;
   Question    : Char;

Procedure Segment(P,Q:Points);
begin
     Deplace(P.x[1],P.x[2]);
     Trace(Q.x[1],Q.x[2]);
end;


Procedure Barycentre(VAR P:Points);
var
   i,j:integer;
   s:Longueur;
begin
     for j:=1 to n do
         begin
              s:=0;
              for i:=1 to k do
                  s:=s+A[i].x[j];
              P.x[j]:=s/k
         end;
end;
Procedure NewPoint(VAR P:points;x:Coordinates;t:string);
var
   j:integer;
begin
     P.t:=t;
     for j:=1 to n do
              P.x[j]:=x[j];
end;

Procedure Vectorise(P,Q:points;VAR v:vecteurs);
var
   j:integer;
begin
     for j:=1 to n do
              v[j]:=Q.x[j]-P.x[j];
end;

Function Scalaire(u,v:vecteurs):Area;
var
   s:Area;
   j:integer;
begin
     s:=0;
     for j:=1 to n do
         s:=s+u[j]*v[j];
     Scalaire:=s;
end;

Procedure Alea(VAR P:Points;t:string);
var
   j:integer;
begin
     P.t:=t;
     for j:=1 to n do P.x[j]:=random;
end;

Procedure MontrePoint(P:Points);
var
   j:integer;
begin
     with P do
     begin
          Croix(x[1],x[2]);
          Ecris(t);
     end;
end;


Procedure Generer(k0:integer);
var
   i:integer;
   t:string;
begin
     k:=k0;
     for i:=1 to k do
         begin
              Str(i,t);
              Alea(A[i],t);
         end;
end;

Function distance2(A,B:Points):Longueur;
var
   j:integer;
   d:MyReal;
begin
     d:=0;
     for j:=1 to n do
         d:=d+sqr(A.x[j]-B.x[j]);
     distance2:=d;
end;

Function distance(A,B:Points):Longueur;
begin
     distance:=sqrt(distance2(A,B));
end;

Function sup(x,y:MyReal):Myreal;
begin
     if x>y then
        sup:=x
     else
         sup:=y;
end;

Function f(M:Points):Longueur;
var
   i:integer;
   d,d1:Area;
begin
     d:=0;
     isup:=1;
     for i:=1 to k do
         begin
              d1:=distance2(M,A[i]);
              if d1>d then
                 begin
                      d:=d1;
                      isup:=i;
                 end;
         end;
     f:=sqrt(d);
end;

Procedure Gradient(M:Points;VAR g:Vecteurs);
var
   i:integer;
   d,d1:Area;
begin
     d:=0;
     isup:=1;
     for i:=1 to k do
         begin
              d1:=distance2(M,A[i]);
              if d1>d then
                 begin
                      d:=d1;
                      isup:=i;
                 end;
         end;
     Vectorise(M,A[isup],g);
end;

Procedure Combine(A,B:Points;y:Myreal;var M:Points);
var
   j:integer;
begin
     for j:=1 to n do
         M.x[j]:=y*B.x[j]+(1-y)*A.x[j];
end;

Procedure Afficher;
Const
     xmin=-0.4;
     xmax=1.5;
     ymin=-0.2;
     var
        i:integer;
begin
     ModeGraphique;
     Efface;
     IsoFenetre(xmin,xmax,ymin);
     Couleur(Vert);
     X_axe(0,0,1);
     Y_axe(0,0,1);
     Couleur(Brillant);
     For i:=1 to k do
      with A[i] do
      begin
           Croix(x[1],x[2]);Ecris(t);
      end;

end;

Procedure Presentation;
begin
    ModeTexte;
    Efface;
    WriteLN('Fraction continue decimale          ');
    WriteLN('                                    ');
    WriteLN('                                    ');
    WriteLN(' (1)   Trac‚ de la figure    ');
    WriteLN(' (2)   Variation de f(M) sur D  ');
    WriteLN(' (3)   Recherche du minimum et des courbes de niveau de f(M)      ');
    WriteLN('                           ');
    WriteLN('                           ');

    InitGraphique;
    ModeTexte;
end;


procedure Question1;

begin
     Efface;
     Writeln('ΙΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝ Question nψ1 ΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝ»');
     Writeln('Ί                                                                   Ί');
     Writeln('Ί  (1)    Trac‚ de la figure                                        Ί');
     Writeln('Ί                                                                   Ί');
     Writeln('ΘΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΌ');

     n:=2;
     Generer(6);
     Afficher;

end;

procedure Question2;

Const
     xmin=-10;
     xmax=10;
     ymin=-1;
     ymax= 10;
     xpas=0.01;
     eps=1E-11;
var
        i:integer;
        x,x1,x2:MyReal;
        A,B,P,Q,M:POints;
        u,g:Vecteurs;

begin
     ModeTexte;
     Efface;
     Writeln('ΙΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝ»');
     Writeln('Ί                                                                   Ί');
     Writeln('Ί  (2)    Variation de f(M)                                         Ί');
     Writeln('Ί                                                                   Ί');
     Writeln('ΘΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΌ');

     n:=2;
     ModeGraphique;
     repeat
           Generer(6);
           Alea(A,'A');
           Alea(B,'B');
           x:=xmin;
           Efface;
           Fenetre(xmin,xmax,ymin,ymax);
     Couleur(Blanc);
     Deplace(xmin,ymax*0.8);
     Ecris(' variation de f(M) si M decrit une droite');
     Couleur(Vert);
     X_axe(0,0,1);
     Y_axe(0,0,1);
     Couleur(Jaune);

     x:=xmin;
     Combine(A,B,x,M);
     Deplace(x,f(M));
     repeat
           Combine(A,B,x,M);
           Trace(x,f(M));
            x:=x+xpas;
     until x>xmax;
     x1:=xmin;
     x2:=xmax;
     Vectorise(A,B,u);
     Couleur(-Brillant);
     Repeat
           x:=(x1+x2)/2;
           Combine(A,B,x,M);
           Gradient(M,G);
           if scalaire(u,G)>0 then
                 x1:=x
              else
                  x2:=x;

           Couleur(-Brillant);
           Cercle(x,f(M),0.2);
           Delay(500);
           Cercle(x,f(M),0.2);

        until abs(x1-x2)<eps;
        Cercle(x,f(M),0.2);
        Croix(x,f(M));
        Trace(x,0);
        Pause;
     until false;
end;




procedure Question3;
const
     pas=0.0001;
     eps=0.00001;
var
   i,j,c,count:integer;
   M,M1,Q:Points;
   g:vecteurs;

   procedure Meilleur(P,Q:Points;VAR M:Points);
   const
        eps=1E-10;
   var
      A,B:Points;
      u,g:vecteurs;
      d:longueur;
   begin
        Combine(P,Q,-f(Q)/distance(P,Q),A);
        Combine(P,Q,1+f(P)/distance(P,Q),B);
        Vectorise(P,Q,u);
        Repeat
              Combine(A,B,0.5,M);
              Gradient(M,G);
              if scalaire(u,G)>0 then
                 A:=M
              else
                  B:=M;
        until distance2(A,B)<eps;
   end;

begin
     Efface;
     Writeln('ΙΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝ»');
     Writeln('Ί                                                                   Ί');
     Writeln('Ί   Recherche it‚rative du point M0 et courbes de niveau            Ί');
     Writeln('Ί                                                                   Ί');
     Writeln('ΘΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΝΌ');

     n:=2;
     repeat
           Generer(2+random(6));
           Afficher;
           Couleur(vert);
           Deplace(0.1,1);
           Ecris(' Courbes de niveau de f(M)');
           Couleur(-Brillant);
           Barycentre(M);
           Count:=0;
           Repeat
                 Inc(Count);
                 M1:=M;
                 {explorer dans une direction al‚atoire}
                 for j:=1 to n do
                     Q.x[j]:=M.x[j]+random-0.5;
                 Couleur(-Jaune);
                 Meilleur(M,Q,M);
                 With M do Cercle(x[1],x[2],f(M));
                 With M do Croix(x[1],x[2]);
                 Delay(100);
                 With M do Cercle(x[1],x[2],f(M));
                 With M do Croix(x[1],x[2]);
           until count>100;
           With M do Cercle(x[1],x[2],f(M));
           With M do Croix(x[1],x[2]);
           count:=0;
           Repeat
                 Inc(count);
                 M1:=M;
                 {explorer dans une direction al‚atoire}
                 for j:=1 to n do
                     M.x[j]:=M.x[j]+0.1*(random-0.5);
                 Q:=M;
                 Couleur(2+(Count mod 13));
                 Deplace(0.1,1);
                 Ecris(' Courbes de niveau f(M)=');
                 EcrisReel(f(M));
                 With M do Deplace(x[1],x[2]);
                 c:=0;
                 repeat
                       Inc(c);
                       Gradient(M,G);
                       M1.x[1]:=M.x[1]+pas*(-g[2]);
                       M1.x[2]:=M.x[2]+pas*( g[1]);
                       M:=M1;
                       With M do Trace(x[1],x[2]);
                 until (c>1000) and (distance2(M,Q)<eps);
           until Keypressed;
           ch:=ReadKey;

     until false;
end;
                                                  


begin
  Randomize;
  Initgraphique;
    while true do
  begin
    Presentation;
     write('Question choisie ? ');
     readln(question);
     case question of
          '1':  Question1;
          '2':  Question2;
          '3':  Question3;
     end;
     Pause;
  end;
end.