Witam.
Mam pewien problem z napisaniem projektu na uczelnie. Należy wygenerować n punktów. poźniej znaleźć dwa okręgi zawierające w sobie wszystkie punkty( przynajmniej 3 punkty mają być na okręgu). Sprawdzić który okrąg ma mniejszą powierzchnie. Problem pojawia się w znalezieniu trzech takich punktów aby okrąg na nich opisany obejmował resztę. Jeśli ktoś ma jakiś pomysł to byłbym wdzięczny.
No chybam że jest jeszcze jedna możliwość, i nie zrozumiałem polecenia, które jest po angielsku ;) Oto ono: "Generate by random a set of n points in 2D Cartesian Coordinates System. Find two different circles enveloping all of the points and connected to the set (there are at least three points on the circle). Check which circle has a smaller area."
Ja próbowałem to rozwiązać w taki sposób, że wybieram 4 punkty o ( najniższa / najwyższa watość X i najniższa / najwyższa wartość Y ) i na tej podstawie dobieranie 3 punktów do okręgów no ale niestety to nie działa (co było do przewidzenia w sumie :( ). DZiękuje za pomoc ;)
- Rejestracja:około 10 lat
- Ostatnio:prawie 10 lat
- Postów:2
C 
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
To jest bez sensu bo można spokojnie wygenerować N punktów z których żadne 3 nie będą znajdować się na tym samym okręgu, ot wystarczyłoby żeby generować wszystkie punkty na tej samej prostej.
- Rejestracja:prawie 16 lat
- Ostatnio:5 miesięcy
- Postów:2514
Nie jestem pewien czy to zadanie jest do końca dobrze sprecyzowane.
a) dwa koła, które w sumie obejmują wszystkie punkty?
czy może
b) dwa różne koła, każde z nich obejmuje wszystkie punkty
W przypadku a):
Ja bym problem uprościł: Wybierz 4 punkty z danego setu punktów w takie sposób, żeby stworzyły czworokąt, który zawiera wszystkie punkty. Czworokąt podziel na dwa trójkąty. Znając punkty obu trójkątów:
http://www.algorytm.org/geometria-obliczeniowa/okrag-przechodzacy-przez-dane-trzy-punkty.html
Wydaje mi się, że nie zawsze da się to zrobić tak, żeby każde z kół zawierało 3 punkty z setu: np. dziewięciokąt wypukły nie foremny.
W dowolnym przypadku wydaje mi się, że rozwiązanie będzie wymagało znalezienia otoczki wypukłej, po czym brut forcem znalezieniu koła (podejrzewam, że dało by rade go troche zoptymalizować, żeby w normalnym czasie liczył). Na czuja wydaje mi się, że powinieneś brać dwa kolejne punkty z otoczki i szukać najbardziej oddalonego od tej pary (odcinka) punktu. (N log N, N - liczba punktow na otoczce)
- Rejestracja:około 17 lat
- Ostatnio:15 dni
- Obliczasz otoczkę wypukłą https://pl.wikipedia.org/wiki/Otoczka_wypuk%C5%82a.
- Wybierasz 3 punkty, które są od siebie oddalone najbardziej (budują największy trójkąt).
- Opisujesz trójkąt na tym punkcie.
Chyba to będzie algorytm optymalny.