Aliens

[novinsky1]

Hej, jakiś pomysł na to zadanie?

SPOJ.com - Problem ALIENS

Próbowałem znaleźć najbliższy oraz najdalszy punkt od początku układu współrzędnych,
następnie obliczyć odległość między tymi punktami, podzielić przez 2, wyszedł mi promień okręgu, następnie wyznaczyłem ze wzoru współrzędne środka okręgu między tymi dwoma punktami.

ALIENS - zadanie

wynik trochę inny niż oczekiwany w zadaniu
jakieś sugestie jak to ogarnąć?

[m_labanowicz]

Czesc,

następnie obliczyć odległość między tymi punktami, podzielić przez 2, wyszedł mi promień okręgu, następnie wyznaczyłem ze wzoru współrzędne środka okręgu między tymi dwoma punktami.

Dla takich 3 punktow wynik nie bedzie prawidlowy:

A (-4,0)
B ( 4,0)
C ( 0,5)

Wg tego rozwiazania, to moga to byc A i C, wtedy okrag nie zalapie punktu B.

Jezeli wezmiemy najdalej od siebie polozne punkty, czyli A i B, |AB|=8
wtedy okrag o promieniu r=4 i śr=(0,0) nie zalapie punktu C.

---

Nie sprawdzalem, takie moje dywagacje, ze moze sprobowac zawrzec wszystkie te punkty w jakims prostokacie, a pozniej opisac na nim okrag.
UPDATE: To nie zadziala dla danych przykladowych

---

Obstawiam, że może być tu potrzebne wygenerowanie otoczki wypukłej + wyznaczenie jej środka (może Centroid’u ?), wtedy mając środek, promień jest juz łatwo obliczyć. To tylko takie pomysły, które mogą nie mieć nic wspólnego z poprawnym rozwiązaniem.

[korkirw]

Nie rozwiązywałem tego zadania, ale wydaje mi się, że to co napisałeś ma sens z matematycznego punkt widzenia. A więc taki schemat jaki podałeś:

1. Wyznaczenie minimalnego wielokąta wypukłego zawierającego wszystkie punkty
2. Wyznaczenie centroidu (lub jak kto woli środka masy) tego wielokąta
3. Wyznaczenie odległości najbardziej odległego punktu od środka masy (to będzie promień)

Mi się wydaje, że matematycznie ta procedura jest poprawna. Natomiast co odpowiedzi na pytanie czy tą drogą da się napisać optymalny (lub chociażby wystarczający) algorytm to moja intuicja odwraca się do mnie tyłem

[quenthui]

To jest znany problem: https://en.wikipedia.org/wiki/Smallest-circle_problem z liniowym rozwiązaniem, jednak napisanie tego nie jest takie oczywiste. Strzelanie w środek otoczki, czy środek przecięcia dwóch najdalszych punktów nie zadziała dla wszystkich przypadków.

[narbej]

@quenthui zastanawiałem się czemu Ci nie dać serduszka i może Ci jeszcze dam. Nie nazwałby jednak w tym kontekście, że to jest znany problem, ale raczej, że ten problem [algorytm] jest opisany tu i tu. Nawet tam jeszcze nie zaglądałem, bo najpierw chciałbym ewentualnie trochę powalczyć z tym “znanym” problemem" samodzielnie. Ale na razie muszę odtajać po dzisiejszym “marszu śledzi”.

A teraz uwagi dla pytającego. Rozwiązując zadanie powinno się dokładnie przeczytać treść zadania, a z niej jasno wynika że punkty nie leżą w I ćwiartce. Nawet gdyby leżały, to twój sposób “wysypie się” dla pkt np: 0,0; 2,0; 0,2. Oczywiście w tym zadaniu nie zawsze rozwiązaniem są dwa najdalsze punkty leżące na średnicy okręgu. Warto posłużyć się rysunkiem albo odręcznym albo w programie graficznym. Jeżeli już nie masz pomysłu, zanim zadasz pytanie, warto przeszukać forum, czy już nie ma wątku/wątków na ten temat i poczytać je!!!

Nie wiem też, czy zdajesz sobie sprawę, że istnieją pl.spoj.com; spoj.com oraz kilka innych wersji językowych i innych odmian spoja - np na najkrótszy kod, wprowadzenie do programowania itd …, a także odpowiednie fora - polskie, angielskie …

[novinsky1]

To bardziej matematyczny problem, nie musisz mnie odsyłać na inne fora, treść czytałem ale miałem problem z wymyśleniem algorytmu nie wiedząc że problem jest już znany, dlatego zapytałem

[narbej]

O Jezu, że tak sobie pozwolę westchnąć.
Przecież Cię nigdzie nie odsyłałem, twierdząc że to problem mniej czy bardziej matematyczny czy też, że problem jest znany czy też nie. Dla mnie jest nie znany.

Chodziło mi o: http://discuss.spoj.com/search?q=aliens <-- chociaż nie mam pojęcia, czy jest tam cokolwiek wartościowego i przydatnego.

Jeżeli chodzi o “marsz śledzi”, to dla nie wtajemniczonych: http://www.marszsledzia.pl/, lub ze słowami krytyki: https://pl.wikipedia.org/wiki/Marsz_Śledzia

[korkirw]

Nie słyszałem do tej pory o “marszu śledzi”. Impreza sprawia wrażenie bardzo pozytywnej. Gratuluję wykonania tego wyzwania, podejrzewam, że mogło być troszeczkę chłodno, ale myślę, ze typowo marynarski napój pomógł przetrwać najgorsze