PROGRAM Escargot;

{
Epreuve informatique de l'Ecole Polytechnique                   93.160


1°  Dans un espace euclidien de dimension n désigné par E, on
associe à tout couple de points A et B un vecteur noté AB et une
distance notée AB. Le produit scalaire de deux vecteurs u et v se
note u.v . Soit S l'ensemble des applications de E dans lui-même qui
ont la propriété de conserver l'angle Ú formé par deux vecteurs
quelconques AB et CD :


Montrer que S muni de la loi de composition des applications forme
un groupe, que l'on appellera "groupe des similitudes". Montrer
qu'il est possible de décrire chaque similitude par un certain
nombre de paramètres, que l'on explicitera dans les cas cas n=2 et
n=3. Ecrire un programme Pascal permettant de calculer l'image de
tout point de E par une similitude s ainsi décrite. Illustrer en
traçant une figure asymétrique (la lettre "F" par exemple) de E et
son image  par les différentes similitudes obtenues en itérant i
fois s.

2°  On considère les applications f définies dans E3 qui ont la
propriété (P) d'être invariantes par similitude :

(P)        f(A,B,C)=f(s(A),s(B),s(C))

Chercher des exemples simples. Ecrire un programme Pascal qui teste
si une application f que l'on sait calculer pour tout élément de E3
possède cette propriété et l'utiliser pour vérifier que certaines
valeurs des coefficients réels Ó, ß, þ lambda et µ, donnent cette
propriété aux fonctions réelles f1 et f2 :

f1(A,B,C)=Scalaire(AB,AC)/(OA²+OB²+OC²-lambda(OA+OB+OC)²)

f2(A,B,C)=Scalaire(AB,AC)/(ÓOA+ßOB+þOC)µ


où O est un point quelconque de E.


3°  On suppose désormais que D=f(A,B,C) est à valeurs dans E tout en
possédant la propriété (P). Donner des exemples variés et montrer
que dans le cas n=2, il existe sauf exception pour chaque f une
expression canonique de la forme :

AD=phi(r,s,t)AB+psi(r,s,t)AC   où  r=AC/AB s=signe(AB/\AC) et t=cos(BAC)

Traiter les exemples suivants :
Cas n°1 : le point D est le symétrique de C par rapport à la droite AB
Cas n°2 : le point D est le centre du cercle inscrit dans le triangle ABC

4°  Ecrire un programme Pascal pour étudier dans le cas n=3 la
convergence éventuelle de la suite de points Mn définis par
récurrence par l'équation Mk+3= f(Mk, Mk+1, Mk+2 ) où les trois
premiers points M0, M1,M2 sont fixés. Discuter la convergence en
fonction des paramètres Ó, ß, þ dans le cas où :

D=f(A,B,C)   AD=(Ó/BC)AB/\AC+ ßAB+ þAC

+------------------------------------------------------------+
¦              Imprimer tous les résultats                   ¦
¦     en indiquant chaque fois à quoi ils correspondent      ¦
+------------------------------------------------------------+

                            -=-=-=-
 }



uses
  crt, graph, modubase,matric



TYPE
    Angle = real;
    Points = record
              x,y,z :real;
              t  : string[1]
            end

    Vecteur = record
                 x,y,z :real
              end;

    Matrice = array[1..3,1..3] of real;

    Arete = Record
                p1,p2 : ^points
            end ;

    Similitude3 = record
                     pivot    : Points;
                     omega    : vecteur;  { module=angle de rotation}
                     lambda   : real;
                     retourne : Boolean;
                     mat_rot  : Matrice;
                  end;

    Similitude=Similitude3;
Const
     reduction = 1;
     n=3;
     O:points=(x:0;y:0;z:0);
VAR
     Car         : Char ;
     Question    : Char;
     W,Px,Py,Pz  : Points;
     Sommet      : Array[1..20] of Points;
     Xmin, Xmax,Ymin,Ymax, yv : real;
     Das         : integer;
     i           : integer;
     alpha,beta,gamma,lambda      :real;

Procedure NewPoint(VAR p:points;x,y,z:real;t:string);
begin
     p.x := x;
     p.y := y;
     p.z := z;
     p.t := t;
end;

Procedure Alea_P(VAR p:points);
begin
     p.x := random*2-1;
     p.y := random*2-1;
     p.z := random*2-1;
end;


Procedure Vectorise(VAR A:Vecteur;P1,P2:Points);
BEGIN
     With A DO
    Dÿ     BEGIN
               x:=P2.x-P1.x;
             @y:=P2.y-P1.y;
               z:=P2.z-P1.z;
          END;
END;

Procedure Translate(A:Vecteur;P1:Points;Var P2:Points);
begin
     P2.x:=P1.x+A.x;
     P2.y:=P1.y+A.y;
     P2.z:=P1.z+A.z;
end;

Procedure Homothetie(lambda:real;v1:Vecteur;Var v2:Vecteur);
begin
     v2.x:=v1.x*lambda;
     v2.y:=v1.y*lambda;
     v2.z:=v1.z*lambda;
end;

Function Module2(V:Vecteur):Real;
BEGIN
     With V do
          Module2 := SQR(x)+SQR(y)+SQR(z);

END;

Function Module(v:Vecteur):Real;
BEGIN
     Module := SQRT(Module2(v));
END;

Function Distance(A,B:Points):Real;
VAR
   v:vecteur;
BEGIN
     Vectorise(V,A,B);
     Distance := Module(v);

END;


PROCEDURE Normalise(VAR v:vecteur);
VAR
   Module : Real;
begin
     With v do
          begin
               Module := SQRT(SQR(x)+SQR(y)+SQR(z));
               x := x/Module;
               y := y/Module;
               z := z/Module;
          end;
end;

Function ProjX(p:points):real;
begin
     ProjX := (p.y-p.x*0.15)*reduction;
end;

Function ProjY(p:points):real;
begin
     ProjY := (p.z-p.x*0.32)*reduction;
end;

Procedure TracePoint(p:points);
VAR
   x,y : real;
begin
     x := ProjX(p);
     y := ProjY(p);
     croix(x,y);
     Ecris(p.t);
end ;


Procedure TraceTrait(p1,p2:Points);
BEGIN
      Deplace(ProjX(p1),ProjY(p1));
      Trace(ProjX(p2),ProjY(p2));
END;


Procedure TraceAxe(x,y,z:real;t:string);
VAR
   p : points;
begin
     NewPoint(p,x,y,z,t);
     TraceTrait(W,p);
     Croix(ProjX(p),ProjY(p));
     Ecris(t);
end;




Procedure Add_vec(V,W:Vecteur;VAR U:Vecteur);
begin
     With U do
          begin
               x := V.x+W.x;
               y := V.y+W.y;
               z := V.z+W.z;
          end;
end;


Procedure Vectoriel(V,W:Vecteur;VAR U:Vecteur);
begin
     With U do
          begin
               x := V.y*W.z-V.z*W.y;
               y := V.z*W.x-V.x*W.z
               z := V.x*W.y-V.y*W.x;
          end;
end;

Function Scalaire(u,v:Vecteur):Real;
BEGIN
     Scalaire := u.x*v.x+u.y*v.y+u.z*v.z;
END;

Function determinant(m:matrice):real;
begin
     determinant:=
                  m[1,1]*(m[2,2]*m[3,3]-m[2,3]*m[3,2])
                + m[1,2]*(m[2,3]*m[3,1]-m[2,1]*m[3,3])
                + m[1,3]*(m[2,1]*m[3,2]-m[2,2]*m[3,1]);

end;



Procedure Mat_Vec(m:matrice;u:vecteur;Var v:vecteur);
begin
     with u do
       begin
            v.x:=m[1,1]*x+m[1,2]*y+m[1,3]*z;
            v.y:=m[2,1]*x+m[2,2]*y+m[2,3]*z;
            v.z:=m[3,1]*x+m[3,2]*y+m[3,3]*z;
       end;

end;


Procedure Barycentre(A,B,C:points;VAR G:Points);
begin
     G.x:=(A.x+B.x+C.x)/3;
     G.y:=(A.y+B.y+C.y)/3;
     G.z:=(A.z+B.z+C.z)/3;
end;

Function Aire(A,B,C:points):real;
Var
   u,v,w:vecteur;
begin
     Vectorise(u,A,B);
     Vectorise(v,A,C);
     Vectoriel(u,v,w);
     Aire:=Module(w)/2;
end;

 { (1)   D symétrique de C par rapport à la droite AB   }
 { (2)   D est le centre du cercle inscrit dans le triangle ABC   }

Function phi(r,s:real):real;
begin
     case cas of
     1: phi:= 2*r*s;
     2: phi:=r/(r+1+sqrt(1+sqr(r)-2*r*s));
    end; {esac}
end;

Function psi(r,s:real):real;
begin
     case cas of
     1: psi:=-1;
     2: psi:=1/(r+1+sqrt(1+sqr(r)-2*r*s));
    end; {esac}
end;

Function r(u,v:vecteur):real;
begin
     if module(u)=0 then
        r:=0
     else
         r:=module(v)/module(u);
end;

Function s(u,v:vecteur):real;
var
   u1,v1:real;
begin
     u1:=module(u);
     v1:=module(v);
     if (u1=0)or(v1=0)then
        s:=0
     else
         s:=scalaire(u,v)/(u1*v1);
end;

Procedure Applique_f2(A,B,C:points;var D:Points);
Var
   u,v,w:vecteur;
   u1,v1:vecteur;
begin
     Vectorise(u,A,B);
     Vectorise(v,A,C);
     homothetie(phi(r(u,v),s(u,v)),u,u1);
     homothetie(psi(r(u,v),s(u,v)),v,v1);
     Add_vec(u1,v1,w);
     Translate(w,A,D);
end;

Procedure Applique_f(A,B,C:points;var D:Points);
Var
   u,v,w:vecteur;
begin
     case cas of
     1:
       begin        {barycentre  }
            D.x:=(A.x+B.x+C.x)/3;
            D.y:=(A.y+B.y+C.y)/3;
            D.z:=(A.z+B.z+C.z)/3;
       end;
     2:begin
            D.x:=(1-beta-gamma)*A.x+beta*B.x+gamma*C.x;
            D.y:=(1-beta-gamma)*A.y+beta*B.y+gamma*C.y;
            D.z:=(1-beta-gamma)*A.z+beta*B.z+gamma*C.z;
            Vectorise(u,A,B);
            Vectorise(v,A,C);
            Vectoriel(u,v,w)
            if distance(B,C)>0 then
               Homothetie(alpha/distance(B,C),w,w);
            Translate(w,D,D);
       end;
     end;  {esac}
end;

Procedure Applique_similitude(A:points;VAR SA:Points;s:Similitude);
                                           {   SA=s(A) }

Var
   u:vecteur;
begin
    with s do
     begin
          vectorise(u,Pivot,A);
          if retourne then
             u.x:=-u.x;
          Mat_vec(mat_rot,u,u);
          Homothetie(lambda,u,u);
          Translate(u,Pivot,SA);
     end;
end;


procedure init(titre:string);
begin
     Modegraphique;
     Efface;
     Xmin := -3;
     Xmax := +4;
     Ymin := -2;
     Ymax := 2;
     Fenetre(Xmin,Xmax,Ymin,Ymax);
     yv := 1.2;
     Deplace(Xmin,Ymin*0.9);
     Ecris(Titre);

     SetBkColor(Blue);

     Couleur(Rouge);
     NewPoint(W,0,0,0,'W');
     TracePoint(W);
     TraceAxe(1.2,0,0,'x');
     TraceAxe(0,1.2,0,'y');
     TraceAxe(0,0,1.2,'z');

     Couleur(-Brillant);
end;                     (* init *)

Procedure gen_mat_rot(omega:Vecteur;VAR m:matrice);
Var
   theta:Angle;
begin
     theta:=module(omega);
     Normalise(omega);
     with omega do
          begin
               m[1,1]:=  cos(theta)+sqr(x)*(1-cos(theta));
               m[2,2]:=  cos(theta)+sqr(y)*(1-cos(theta));
               m[3,3]:=  cos(theta)+sqr(z)*(1-cos(theta));

               m[1,2]:= x*y*(1-cos(theta))+z*sin(theta);
               m[2,1]:= x*y*(1-cos(theta))-z*sin(theta);

               m[1,3]:= x*z*(1-cos(theta))-y*sin(theta);
               m[3,1]:= x*z*(1-cos(theta))+y*sin(theta);

               m[2,3]:= y*z*(1-cos(theta))+x*sin(theta);
               m[3,2]:= y*z*(1-cos(theta))-x*sin(theta);
          end;
end;





Procedure Question1;
Var
   i:integer;
   A,SA,M:Points;
   motif:array [1..5] of points;
   s:similitude;
   k:integer;
Const
   imotif:array [1..5] of points=
              ((x:0;y:0;z:0),
               (x:0;y:2;z:0),
               (x:1;y:2;z:0),
               (x:1;y:1;z:0),
               (x:0;y:1;z:0));

begin
     Efface;
     Writeln('+---------------------- Question n°1 -------------------------------+');
     Writeln('¦                                                                   ¦');
     Writeln('¦   Une similitude est définie par                                  ¦');
     Writeln('¦                                             n=2   n=3    n        ¦');
     Writeln('¦   = La position du pivot                      2     3    n        ¦');
     Writeln('¦   + L''isométrie Omega ("rotation")            1     3   n(n-1)/2  ¦');
     Writeln('¦   + un coefficient de similitude Lambda       1     1    1        ¦');
     Writeln('¦   + un retournement éventuel         õ=       4     7  1+n(n+1)/2 ¦');
     Writeln('+-------------------------------------------------------------------+');
     Pause;
     Randomize;
     Init('Similitude');
     with s do
          begin
              Pivot.x:=Random;
              Pivot.y:=Random;
              Pivot.z:=Random;
              deplace(xmin,ymax*0.70);
              ecris('Pivot x=');ecrisreel(Pivot.x);
              ecris     (' y=');ecrisreel(Pivot.y);
              ecris     (' z=');ecrisreel(Pivot.z);
              Omega.x:=Random;
              Omega.y:=Random;
              Omega.z:=Random;
              deplace(xmin,ymax*0.60);
              ecris('Omega x=');ecrisreel(Omega.x);
              ecris     (' y=');ecrisreel(Omega.y);
              ecris     (' z=');ecrisreel(Omega.z);
              Lambda:=random*1.2;
              deplace(xmin,ymax*0.50);
              ecris('Lambda=');ecrisreel(Lambda);
              retourne:=(random<0.5);
              Gen_Mat_rot(omega,mat_rot);
          end;

     for i:=1 to 5 do
         motif[i]:=imotif[i];
     k:=0;
     repeat
           M:=motif[2];
           Delay(1000);
           Inc(k);
           Couleur(Jaune);
           deplace(xmin,ymax*0.40);
           ecris('k=');ecrisentier(k);
           for i:=1 to 4 do
             TraceTrait(motif[i],motif[i+1]);
           for i:=1 to 5 do
               Applique_similitude(motif[i],motif[i],s);
           Couleur(Brillant);
           TraceTrait(M,motif[2]);
    until KeyPressed;
    Car:=readKey;

end;

Procedure Question2;
Var
   i,k:integer;
   M:array[0..3] of Points;
   x,y,z:real;
begin
     Efface;
     Writeln('+---------------------- Question n°2 -------------------------------+');
     Writeln('¦                                                                   ¦');
     Writeln('¦   Calcul itératif de Mk+3=f(Mk+2,Mk+1,Mk)   dans R2               ¦');
     Writeln('¦                      D=f(A,B,C)                                   ¦');
     Writeln('¦                                                                   ¦');
     Writeln('¦   AD=phi(r,s)AB+psi(r,s)AC                                        ¦');
     Writeln('¦                                                                   ¦');
     Writeln('¦       où  r=AC/AB     et   s=Scal(AB.AC)/(AB.AC)                  ¦');
     Writeln('¦                                                                   ¦');
     Writeln('¦   (1) D symétrique de C par rapport à la droite AB                ¦');
     Writeln('¦   (2) D est le centre du cercle inscrit dans le triangle ABC      ¦');
     Writeln('+-------------------------------------------------------------------+');
     repeat
           write('Cas choisi ? ');
           readln(cas);
     until cas in [1..2];

     Randomize;
     repeat
          case cas of
          1:Init('(1) D symétrique de C par rapport à la droite AB ');
          2:Init('(2) D est le centre du cercle inscrit dans le triangle ABC');
          end; {esac}
           for i:=1 to 3 do
               begin
                    Alea_P(M[i]);
                    M[i].z:=0;
               end;

           TraceTrait(M[1],M[2]);
           TraceTrait(M[2],M[3]);

           alpha :=4*random-2;
           beta  :=random;
           gamma :=random;

           y:=1;
           k:=0;
           repeat
                 Inc(k);
                 Couleur(Jaune);
                 deplace(xmin,ymax*0.55);
                 ecris('k=');ecrisentier(k);
                 deplace(xmin,ymax*0.50); ecris(' alpha=');ecrisreel(alpha);
                 deplace(xmin,ymax*0.45); ecris(' beta =');ecrisreel(beta );
                 deplace(xmin,ymax*0.40); ecris(' gamma=');ecrisreel(gamma);
                 Couleur(-Brillant);


                 for i:=1 to 3 do
                     M[i-1]:=M[i];
                 Applique_f2(M[0],M[1],M[2],M[3]);
                 TraceTrait(M[2],M[3]);

                 deplace(xmin,ymax*0.90);
ecris('BC/AB=');ecrisreel(distance(M[2],M[3])/distance(M[1],M[2]));
                 deplace(xmin,ymax*0.85);
ecris('BC/AC=');ecrisreel(distance(M[2],M[3])/distance(M[1],M[3]));
                 deplace(xmin,ymax*0.80);
                      ecris(' x=');ecrisreel(M[3].x);
                      ecris(' y=');ecrisreel(M[3].y);
                      ecris(' z=');ecrisreel(M[3].z);
                 Delay(1000);
           until KeyPressed;
           Car:=readkey;
     until car=#27;
end;


Procedure Question3;
Var
   i,k:integer;
   M:array[0..3] of Points;
   x,y,z:real;
begin
     Efface;
     Writeln('+---------------------- Question n°3 -------------------------------+');
     Writeln('¦                                                                   ¦');
     Writeln('¦   Calcul itératif de Mk+3=f(Mk+2,Mk+1,Mk)   dans R3               ¦');
     Writeln('¦                      D=f(A,B,C)                                   ¦');
     Writeln('¦                                                                   ¦');
     Writeln('¦   (1) Barycentre                                                  ¦');
     Writeln('¦   (2) AD=(Ó/BC)(AB/\AC)+ßAB+þAC                                   ¦');
     Writeln('+-------------------------------------------------------------------+');
     repeat
           write('Cas choisi ? ');
           readln(cas);
     until cas in [1..2];

     Randomize;
     repeat
          case cas of
          1:begin
                 Init('(1) Barycentre');
                 alpha :=random;
                 beta  :=random;
                 gamma :=random;
                 x:=alpha+beta+gamma;
                 alpha:=alpha/x;
                 beta  :=beta/x;
                 gamma :=gamma/x;
            end;
          2:begin
                 Init('(2) AD=(Ó/BC)(AB/\AC)+ßAB+þAC');
                 alpha :=4*random-2;
                 beta  :=random;
                 gamma :=random;
            end;
          end; {esac}
           for i:=1 to 3 do
               Alea_P(M[i]);
           TraceTrait(M[1],M[2]);
           TraceTrait(M[2],M[3]);


           k:=0;
           repeat
                 Inc(k);
                 Couleur(Jaune);
                 deplace(xmin,ymax*0.55);
                 ecris('k=');ecrisentier(k);
                 deplace(xmin,ymax*0.50); ecris(' alpha=');ecrisreel(alpha);
                 deplace(xmin,ymax*0.45); ecris(' beta =');ecrisreel(beta );
                 deplace(xmin,ymax*0.40); ecris(' gamma=');ecrisreel(gamma);
                 Couleur(-Brillant);


                 for i:=1 to 3 do
                     M[i-1]:=M[i];
                 Applique_f(M[0],M[1],M[2],M[3]);
                 TraceTrait(M[2],M[3]);

                 deplace(xmin,ymax*0.90);
ecris('BC/AB=');ecrisreel(distance(M[2],M[3])/distance(M[1],M[2]));
                 deplace(xmin,ymax*0.85);
ecris('BC/AC=');ecrisreel(distance(M[2],M[3])/distance(M[1],M[3]));
                 deplace(xmin,ymax*0.80);
                      ecris(' x=');ecrisreel(M[3].x);
                      ecris(' y=');ecrisreel(M[3].y);
                      ecris(' z=');ecrisreel(M[3].z);
                 Delay(1000);
           until KeyPressed;
           Car:=readkey;
     until car=#27;
end;





Procedure Presentation;
begin
    ModeTexte;
    Efface;
    WriteLN('      Le limaçon dans E3               ');
    WriteLN('                                       ');
    WriteLN('                                       ');
    WriteLN(' (1)  Similitude P                     ');
    WriteLN(' (2)  Convergence f(A,B,C) dans R2              ');
    WriteLN(' (3)  Convergence f(A,B,C) dans R3              ');
    WriteLN('                                       ');
end;



begin
  Initgraphique;
  for i:=1 to n do
      begin
           O.x:=0;
      end;
  while true do
  begin
     Presentation;
     write('Question choisie ? ');
     readln(question);
     Efface;
     writeln('======== Question n°',question,'===============');
     writeln('');

     case question of
          '1':  Question1;
          '2':  Question2;
          '3' : Question3;
     end;
  end;

end.