NAJBLPKT - Najbliższa para punktów

[jedrzejd]

Witam sędzia akceptuje, oto kod

[mariusz193]

to że nie akceptuje, to oczywiste - pierwiastek z liczby ujemnej trudno policzyć

niestety po poprawieniu tego drobiazgu jest TLE, a ponieważ nigdy nie przerabiałem tego algorytmu (zawsze wydawał mi się zbyt trudny, a dodatkowo nie mam zaufania do rekurencji) to już nie potrafię pomóc

[tarpauwatratar]

NAJBLPKT - Najbliższa para punktów

Treść Zadania [http://pl.spoj.com/problems/NAJBLPKT/] Implementacja własna [https://ideone.com/IklCr4] Implementacja STL’owa [https://ideone.com/ba8XqG] Gotowiec z neta [https://www.geeksforgeeks.org/closest-pair-of-points/] Nie wiem dlaczego moje podejście do tego zadania jest błędne. Wydawało mi się, że znam algorytm na najbliższą parę punktów metodą podziału zbioru (zamiatania prostą nie znam, ale jak ktoś ma ładny link to chętnie poznam w wolnym czasie), ale jak widać po zgłoszeniach chy…

Nie wiem, czy ktoś Ci pomoże. Zadanie jest wredne. Robiłem je dawno temu i pamiętam, że nie jeden zachwalany gotowiec z sieci / sposób implementacji dał WA / TLE.

Osobiście wykorzystałem je do zapoznania się z ideami stosowanymi przez osoby zawodowo trzaskające zadania algorytmiczne i rozwiązałem wykorzystując materiały linkowane w temacie: Nauka programowania i nie tylko -> 10 darmowych stron. Link do strony, na której był gotowiec, dalej tam jest (ale nie zagwarantuję, że kod wciąż będzie dostępny).

W moim zgłoszeniu AC jest nawet komentarz “NAJLEPSZE W CALYM NECIE” więc chyba faktycznie warto to przeanalizować, a całkowicie samodzielne zaklepanie algorytmu zostawić na inną okazję (a tych pewnie nie braknie), ale oczywiście to tylko moja opinia.

[jedrzejd]

Ale przecież suma kwadratów jest zawsze nieujemna
To w jaki sposób może wychodzić liczą ujemna pod pierwiastkiem.

[mariusz193]

Ale przecież suma kwadratów jest zawsze nieujemna

To w jaki sposób może wychodzić liczą ujemna pod pierwiastkiem.

dla ciebie tak, dla mnie też - ale procesor może mieć na ten temat inne zdanie

[jedrzejd]

Jakim cudem procesor może w obliczeniach wyjść liczba ujemna jeżeli chyba dobrze rozpoznaje operacje — razy — to + to chyba nie wyjdzie nigdy mu -x*-x= -x^2

[redysz]

@jedrzejd To co napisałeś to punkt patrzenia matematyki. Jednak podejrzewam, że mariuszowi chodziło o coś innego:

Mam zmienną 1.1
Drugą zmienną równą -0.9
Trzecią 0.2
Jaki jest wynik działania 1.1 + (-0.9) - 0.2? Dla matematyki jest to 0. Dla procesora:
sprawdź sam
A przestawiając działania (co nie powinno wpłynąć na wynik) możemy otrzymać:
całkiem inny

Czyli: operacje zmiennoprzecinkowe nie są dokładne (jak w matematyce), a co za tym idzie można wyjść poza granice rozsądnego wyniku.

Edit: O a jednak chodziło o zakres wartości typów danych

[mariusz193]

Jakim cudem procesor może w obliczeniach wyjść liczba ujemna jeżeli chyba dobrze rozpoznaje operacje — razy — to + to chyba nie wyjdzie nigdy mu -x*-x= -x^2

chyba nie przeczytałeś początkowych rozdziałów z podręcznika C/C++
one wydają się całkowicie nieistotne, ale potem niektórzy się dziwią, że komputer daje inny wynik, niż oczekują

zamieściłeś przykład, to teraz pomnóż wszystkie te współrzędne przez 10000 (10 tysięcy) i zobacz wynik - a potem wróć do podręcznika - poczytaj o typach zmiennych, ich zakresach, rzutowaniach i automatycznej konwersji

prawdę mówiąc dziwię się, że ktoś kto implementuje całkiem trudny algorytm nie zna podstaw programowania (chyba że obecnie te początkowe rozdziały usunięto z podręczników, dawno nie zaglądałem do jakiegokolwiek podręcznika programowania)

[jedrzejd]

Dobra jest AC .
Mój duży błąd, że nie doczytałem max rozmiaru współrzednych w treści zadania
Wynik przekręcał się na minusa.
Nie zrozumiałem na początku o co chodzi

to oczywiste - pierwiastek z liczby ujemnej trudno policzyć

Dopiero gdy przeczytałem:

to teraz pomnóż wszystkie te współrzędne przez 10000

Zajrzałem na zakresy wejścia.

[jedrzejd]

Mam zmienną 1.1
Drugą zmienną równą -0.9
Trzecią 0.2
Jaki jest wynik działania 1.1 + (-0.9) - 0.2? Dla matematyki jest to 0. Dla procesora:
sprawdź sam
A przestawiając działania (co nie powinno wpłynąć na wynik) możemy otrzymać:
całkiem inny

Dziwne jak zamienie na printf to dobrze liczy

Ideone.com

[redysz]

Dziwne jak zamienie na printf to dobrze liczy

Bo coś mało cyfr wyświetla, różnica siedzi o wiele dalej. Tak samo będzie jak dodasz jakąś małą liczbę: sprawdź, a pomyłka była na pozycji e^-17