Bonjour,
 
Je souhaite resoudre un challenge informatique, je dois trouver le point dans un triangle de 273 metres de coté qui est a des distances EXACTES des sommets. Pour trouver ce point j'ai faitun programme en maple (langage plus simple pour les calculs mathematiques que le C).
 
trianglesuper := proc ()::list;
local x::integer, y::integer, a::float, b::float, c::float;
for x to 273 do
for y to 84 do
if y < 2*x and y < -2*x+223587 then
a := sqrt(x^2+y^2);  
b := sqrt((273*abs(sin(60))-y)^2+(273/2-x)^2);
c := sqrt((x-273)^2+y^2);  
if floor(a)-a = 0 and floor(b)-b = 0 and floor(c)-c = 0
then return evalf([a, b, c])
end if  
end if  
end do
end do  
end proc
 
J'ai modelise mon triangle dans un repere. Un des cotés se trouve sur l'axe X donc x peut aller de 0 a 273.
Les deux autres cotés sont des fonctions (2x) et (-2x+223587) car la pente de la fonction 2x fait un angle de 60° avec l'axe x et que 223587 est l'ordonée necessaire pour que la fonction coupe l'axe des abcisses en 273.
 
84 est l'ordonée maximale de mon triangle.
 
Donc avec mes boucles je suis dans un carre de 273*84(arrondi de 273*sin60) et grace a mes conditionnelles je suis dans mon triangle normalement (puisque "sous" mes fonctions), ensuite je calcule la distance du point vis a vis des 3 sommets (formules incorrectes pê :x) et si ce sont des valeurs entieres alors je les renvoie sous forme de listes.
 
Lorsque je l'execute il ne me renvoie rien.
 
Qu'ai je mal codé  ?
 
Merci

• les droites de pente 2 et -2 ne font pas un angle de 60° avec l'axe des abscisses
• un test du genre floor(a)-a = 0 risque de ne jamais marcher à cause de la représentation flottante de tes nombres. Essaie avec des tests du genre abs(floor(a) - a) < 1e-5.
• es-tu sûr qu'il existe une solution à ton problème ?
• n'y aurait-il pas une méthode plus intelligente pour résoudre ce problème, plutôt que de faire une recherche exhaustive ? (c'est une question ouverte : je ne sais pas si une telle méthode directe existe)

Un autre problème : est-ce que l'énoncé stipule qu'il faut rechercher des points de coordonnées entières ?

Euh...
 
Triangle de 273 mètres de coté... Angles de 60°... J'en déduit que ton triangle est équilatéral non ?
 
Ben y'a quand même plus simple pour trouver le centre de grativé/orthocentre/centre du cercle circonscrit/centre du cercle inscrit à ton triangle...
 
Je te renvoie à tes cours de 6°...
http://pagesperso-orange.fr/pierre [...] iEqu01.htm
 
Honnêtement, ça se fait en 4 lignes, même en ASM, et pas besoin d'avoir un côté sur l'axe X ou Y...
Utilise simplement la formule du calcul du centre de gravité... Même pas besoin de faire intervenir le moindre calcul à base de sin() et cnie... Deux bêtes addition et deux bonnes divisions par 3 et roule ma poule, je vois pas comment on peut faire plus simple... Ah si, peut-être trouver le centre de gravité d'un point
 
 
/me vient de réalister... Tu cherches peut-être pas le point qui est à la même distance de chaque point, mais celui qui sera à une distance entière de chacun des points c'est ça ?

Oui, je crois que c'est ça...
 
Par contre, ce qui n'est pas clair c'est si on cherche un point de coordonnées entières, ou un point quelconque...

Sinon, moi je ferais pas comme ça.
 
Je dirais que :
- Ton point doit de trouver sur le cercle c1 de centre A et de rayon r1 entier.
- Ton point doit de trouver sur le cercle c2 de centre B et de rayon r2 entier.
- Ton point doit de trouver sur le cercle c3 de centre C et de rayon r3 entier.
 
Donc moi je tenterais de trouver le point d'intersection commun des cercles r1, r2 et r3.
 
Ceci donne d'ailleurs comme conclusion qu'il y a au point 3 points (qui peuvent être confondus) qui répondent au problème.

Il y a plein de cercles de centre A et de rayon r1 entier    
 
Et étant donnés trois rayons entiers r1, r2, r3, rien ne prouve que les 3 cercles sont concourrants.

Y'en a 273 pour être exact.
 
Mais déjà, tu peux partir du principe qu'il ne peux pas être de rayon > que distance avec lecentre de gravité, sinon le point "équivalent" en partant des deux autres somment vient remplacer ceux que tu as déjà fait.
 
Donc.
 

 
Ca me semble être la solution la plus simple.
 
Du moins, c'est la solution "humaine" que 3 maçons peuvent aisément mettre en oeuvre avec chacun une corde attachée à chacun des 3 sommets.
 
Un matheux te trouveras certainement de grosses optimisations évidentes, mais moi et la théorie matheuse... Une corde et un maçon au bout, ça je me le représente, des sqtr(cos(pi/12)) là moi je nage.

Lol ok donc je vais chercher du coté des droites alors.
Pourquoi 1e-5? Mon prof d'algo m'as dit que c'etait correct, apres il se trompe peut etre ..    
En effet il y a surement une methode plus "mathematique" et "logique" mais je ne vois vraiment pas. J'ai eu des echos comme quoi la methode des trois cercles que vous proposez apres fonctionnerait par contre faudrait que je reflechisse a comment le programmer.
 

Oui C'est la toute la difficulté du probleme.
 

Un point quelconque si j'ai bien compris le probleme.
 

Ca me semble interessant mais je ne vois pas comment "regarder si c1, c2 et c3 ont un point d'intersection commun."
 
Je vais reflechir a ca.
 
MErci pour vos reponses.

Entièrement d'accord avec ça. Ce que je remettais en cause, c'est ta "preuve" qu'il y a "au moins trois points qui répondent au problème".
 
 
exeed> le calcul des points d'intersections de deux cercles est vraiment très classique et très simple. Si tu ne veux pas / ne sais pas le faire toi-même, une recherche te donnera rapidement les formules.
 
L'histoire du abs(...)<1e-5 c'est juste pour dire qu'il y a une différence entre la vraie vie et les maths. Dans la vraie vie, les nombres réels sont stockés dans des variables en virgule flottante, les cos et sin sont calculés de manière approchée, etc. Donc un test exact n'a quasiment aucune chance de marcher.
 
Si le point que tu recherches n'a pas forcément des coordonnées entières, oublie ton algo et pars sur celui que te proposes MagicBuzz. Il ya sans doute plein d'optimisations à faire, mais ce sera pour plus tard.

Est ce que le theoreme de Miquel est utile?  
Je vais y penser ...

Non, les théorèmes de Miquel ne servent à mon avis à rien dans ta situatio, puisqu'ils ne parlent pas des centres des cercles concourrants.

un autre algo plus efficace je pense que celui de MagicBuzz :

C'est simple, tu es dans un triangle equilatéral.
 
En gros, quand tu trouves un point p1 avec dA = x, dB = y, dC = z, alors il existe aussi un point p2 avec dA = y, dB = z, dC = x et un point p3 avec dA = z, dB = x, dC = y.
 
Le seul cas où il n'y a pas 3 points, c'est si x = y = z, et que ton point est le centre de gravité (et donc les trois points sont confondus).
 
Ceci dit, un triangle équilatéral étant symétrique, je dois dire qu'en fait il y a non pas 3 points mais 6 points qui répondent à la question, puisque p4 (dA= x, dB = z, dC = y), p5 (dA = y, dB = x, dC = z) et p6 (dA = z, dB = y, dC = x) existent aussi.

En gros, quand t'as trouvé des distances d1, d2 et d3 qui fonctionnent, alors tu peux faire toutes les combinaisons de 3 cercles de rayon d1, d2, d3 en partant de chacun des sommets de ton triangle, il y aura un point d'intersection.
 
Et d'ailleurs, l'inverse est vrai aussi, et peut représenter une très grosse optimisation : pour n'importe quel d1, d2, d3 qui ne marche pas, alors ça ne marchera pas quelque soient les somments centres des cercles ayant pour rayon d1, d2 et d3 (cela devrait te permettre de réduire considérablement les itérations des boucles imbriquées).

OK pour la symétrie : si tu arrives à trouver un point solution, alors en général tu en obtiens d'autres par symétrie. Mais rien ne te prouve qu'il existe un point solution.
 
C'est une hypothèse que tu sembles faire depuis le début et qui est fausse dans le cas général. Considère par exemple un petit triangle équilatéral de côté 10 : tu ne trouveras aucune solution non triviale.

Déjà, y'a 3 points solution qui sont évident à trouver
 
A, B et C sont trois points qui répondent au problème avec d1 = COTE, d2 = COTE et d3 = 0

Chais pas si ça marche (y trouve tous les points ?), mais si c'est bon, ça te donne une version optimisée de mon algo :

using System;
 
namespace TestCercles
{
    class Program
    {
        static void Main(string[] args)
        {
            const double COTE = 273;
 
            Triangle MonTriangle = new Triangle(COTE);
 
            double maxRayon = COTE - 1;
 
            for (double i = 1; i < maxRayon; i++)
            {
                for (double j = COTE - i; j < maxRayon; j++)
                {
                    Point p = MonTriangle.TrouverIntersection(i, j);
                    double k = p.ObtenirDistance(MonTriangle.C);
                    if (Math.Ceiling(k) == k)
                        Console.WriteLine("Le point ({0}, {1}) répond au problème.", p.X, p.Y);
                }
            }
            Console.ReadKey(true);
        }
    }
 
    public class Point
    {
        public double X;
        public double Y;
 
        public Point(double x, double y)
        {
            this.X = x;
            this.Y = y;
        }
 
        public double ObtenirDistance(Point p)
        {
            return Math.Sqrt(Math.Pow(p.X - this.X, 2) + Math.Pow(p.Y - this.Y, 2));
        }
    }
 
    public class Triangle
    {
        public Point A;
        public Point B;
        public Point C;
 
        private double Cote;
 
        public Triangle(double cote)
        {
            this.Cote = cote;
            this.A = new Point(0f, 0f);
            this.B = new Point(cote, 0f);
            this.C = new Point(cote / 2, Math.Sqrt(Math.Pow(cote, 2) - Math.Pow(cote / 2, 2)));
        }
 
        // Trouve le point d'intersection inscrit dans le triangle entre les cercles de rayons r1 et r2 ayant pour sommets A et B (on part du principe qu'il existe forcément !)
        public Point TrouverIntersection(double r1, double r2)
        {
            // (TRES) adapté à partir du code source en C trouvé ici
            // http://local.wasp.uwa.edu.au/~pbou [...] e/tvoght.c
            // ATTENTION : Ce n'est pas du tout l'algo exact. Il s'agit ici d'une version épurée
            // qui ne retourne que le point d'intersection qui se trouve dans le triangle
            // et on part du principe que les deux cercles ont effectivement une intersection.
 
            double a = (Math.Pow(r1, 2) - Math.Pow(r2, 2) + Math.Pow(this.Cote, 2)) / (2 * this.Cote);
            double h = Math.Sqrt(Math.Pow(r1, 2) - (Math.Pow(a, 2)));
            return new Point(a, h);
        }
    }
}

 
Si en plus tu veux les points dont les coordonées sont entières, y'a un petit filtre à rajouter...

sinon, l'algo original, c'était quoi exactement ? parceque je panne rien au code, avec l'algo ce serait peut-être plus clair

eh bah ca travaille merci a vous pour cette aide

OK donc j'ai rajouté un test pour qu'une des coordonnées soient égale a 0 (le point ne peux pas être un des sommets), je tombe donc sur 6 réponses avec 2 trio de distances (qui se répètent donc 3 fois chacun, pas dans le même ordre, l'ordre n'as pas d'importance)
 
Y aurait il des tests supplémentaire a faire?
 
Je ne vois pas comment améliorer l'algorithme pourtant j'y travaille depuis plusieurs heures :x