Logowanie

Połączenie między punktami

pytanie zadane 27 listopada 2016 w Algorytmy przez ProgramistaStepek Nałogowiec (27,020 p.)

Witam. Szukam pomocy w sposobie rozwiązania problemu. Do rzeczy: Jak sprawdzić czy między dwoma punktami w układzie współrzędnych jest połączenie? Zasada jest taka, między dwoma punktami z tą samą pierwszą lub drugą współrzędną np.(1,2) i (1, 6). Jest połączenie a między (3,4) i (5,8) nie ma. Problem nie jest tak trywialny jakby się zdawał a google milczy (albo to ja nie wiem jak znaleźć).

Punktów podanych może być więcej niż dwa np. (1,2), (2,2), (2,3). Trzeba zauważyć, że mimo, iż teoretycznie między punktem pierwszym i trzecim nie ma połączenia, ale "łącznikiem" jest punkt drugi.

komentarz 27 listopada 2016 przez adrian17 Ekspert (344,860 p.)

Czy jak masz dane punkty A, B, C, D, E to konkretnie pytanie brzmi "czy punkty A i E są połączone po kolei łącznikami B, C, D" czy "czy istnieje jakiekolwiek połączenie między A i E"?

komentarz 27 listopada 2016 przez ProgramistaStepek Nałogowiec (27,020 p.)

Pytanie: Czy istnieje połączenie między punktami A i B?

1	komentarz 27 listopada 2016 przez adrian17 Ekspert (344,860 p.) I punktów może być dowolnie dużo (np. 10000), tak? No to ja bym skonstruował graf łączący "połączone" punkty po czym zastosował prosty algorytm szukania drogi, pewnie BFS.

komentarz 27 listopada 2016 przez ProgramistaStepek Nałogowiec (27,020 p.)

O właśnie o to mi chodziło :) Dzięki ☺️

komentarz 28 listopada 2016 przez Jakub Śliż Użytkownik (940 p.)

A jak miałby wyglądać owy graf?

komentarz 29 listopada 2016 przez playerony Pasjonat (15,240 p.)

Pierw trochę terii:

http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_12:_Grafy

Potem coś o macierzach grafów:

http://www.algorytm.org/klasyczne/grafy-i-ich-reprezentacje.html

Pozdro 600

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów

1 odpowiedź 410 wizyt

Obliczanie kąta pomiędzy trzema punktami - Zadanie Autobus OIG

pytanie zadane 21 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

0 głosów

3 odpowiedzi 2,882 wizyt

Sprawdzenie kodu liczącego odległość między punktami

pytanie zadane 6 lipca 2017 w Python przez DODO Bywalec (2,950 p.)

0 głosów

1 odpowiedź 1,081 wizyt

Długość odcinka między dwoma punktami w przestrzeni.

pytanie zadane 15 kwietnia 2017 w JavaScript przez Neespa Początkujący (300 p.)

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...