BitCell

Fie două puncte A şi B de aceeaşi parte a unei drepte d. Să se găsească un punct M care apartine dreptei d astfel încât suma AM+MB sa fie minima.

• Punctele se dau prin coordonatele lor. Ex: A(xa,ya)
• Dreapta este dată prin intermediul a două puncte X, Y (ale caror coordonate sunt cunoscute)

Restricţii şi precizări

• coordonatele punctelor sunt din intervalul [-150000, 500000]
• Datele se citesc din "bitcell21.in" si se scriu in fisierul "bitcell21.out"

Data start: 06/12/2011
Data stop: 13/12/2011
Desemnare castigator: 14/12/2011

Cateva intrebari de siguranta:
- punctele A si B banuiesc ca nu pot sa coincida: TRUE / FALSE ?
- punctele A si B nu se gasesc pe dreapta : TRUE / FALSE ?

Daca vreau sa fac programul intr-un limbaj interpretat, banuiesc ca iti trimit doar sursele .

Problema e mai mult de geometrie, partea de informatica e mai simpla. Personal ma gandesc sa vin cu o solutie JavaScript folosind Canvas-ul din HTML5, sau un applet Java care sa deseneze dreapta si punctele.

Asa ca pentru cresterea "dificultatii" nu ar fi interesant sa pretinzi si o solutie grafica la problema ?

*back to the drawing board*

^^
1. TRUE
2. FALSE

Nu stiu daca ar fi corect sa cer o solutie grafica.

^ Solutia ta pica toate testele.

Am o nelamurire. Ai dat exemplul asta:


In cazul dat, M n-ar fi putut fi, la fel de bine, la coordonatele (0, 0) ? Daca si (0, 0) e o pozitie buna pentru M, atunci datele din fisierul de iesire cum le verifici ? Nu e mai simplu sa ceri distanta minima - ca valoare - in loc de coordonatele punctului M ?

Imi cer scuze... se pare ca am gresit tocmai exemplul. Imi cer scuze daca v-am indus in eroare. Punctul M are coordonatele 2 0.



Exista un singur punct pentru care distanta AM+MB sa fie minima.

Ti-am modificat in primul post

Se pare ca nu avem un castigator. Problema se baza pe cateva observatii matematice:

Fiind data o drapta d si doua puncte de aceeasi parte a dreptei (A si B) trebuia sa se gaseasca un M pe dreapta d astfel incat AM+MB sa fie minima.

Construim A' simetricul lui A fata de dreapta d. De aici putem trage concluzia ca oricare ar fi un punct N pe dreapta d atunci AN=A'N.
Pentru ca distanta dintre A' si B sa fie minima atunci le unim printr-o linie dreapta. Prin urmare punctul cautat (M) se gaseste le intersectia segmentului [A'B] cu dreapta d.

Simetricul punctului P(x0, y0) fata de o dreapta de ecuatie ax+by+c=0 se calculeaza astfel:

Notam cu dist distanta de la punct la dreapta = (|a*x0 + b*y0+c|)/(sqrt(a2+b2)
Notam cu m1, m2 cosinii directori ai vectorului normal la dreapta: m1=+- a/(sqrt(a2+b2) ; m2=+- b/(sqrt(a2+b2). Vom alege semnul - daca ax0+by0+c>0 si semnul + in caz contrar.

Simetricul punctului P va fi:
P' ( x0 +2*dist*m1, y0+ 2*dist*m2).