Witam
Na wstępie chciałbym napisać iż jestem noga z matematyki, a także przeprosić jeśli to zły dział, starałem się trafić jak najlepiej z tematem, bo zależy mi na odpowiedzi, baaardzo.
Zadanie jest następujące.
Mamy X sklepów, których pozycję oznaczamy X1(x1,y1), X2(x2,y2), ... itd.
Są one ustalone raz i nie mogą zostać zmienione.
Mamy Y magazynów, pozycję ich oznaczamy analogicznie Y1(x1,y1), Y2(x2,y2), ... itd.
Magazyny możemy przemieszczać, i należy je ustawić tak aby łączna droga, suma, odległości magazynów od sklepów była jak najmniejsza. Przy założeniu iż każdy sklep łączy się z każdym magazynem.
Tutaj pierwsza uwaga, wydaje mi się iż wykładowca się pomylił, (zadanie wymyślił na poczekaniu, za karę, tylko dla mnie ), bo przecież najmniejsza odległość zawsze będzie gdzieś we wnętrzu figury i nic nie stoi na przeszkodzie aby magazyny były w tym właśnie miejscu wszystkie razem. (nie było mowy iż położenia nie mogą się pokrywać, a nie wiedzę przeciwwskazań).
zatem, zadanie redukuje się do ustalenia gdzie jest ten punkt w figurze o N wierzchołkach dla których suma długości prostych wyprowadzonych do każdego z wierzchołków jest najmniejsza.
Myślę iż chodzi tu o prostą właściwość figur geometrycznych, być może środek figury spełnia tą własność, a może zadanie nie jest takie proste przy X=100, a Y=1000, czy coś przeoczyłem ?
Proszę o wskazówki, jak mówiłem dawno nie miałem kontaktu z matematyką.