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 chyba jednak nie. Stąd też tutaj mój post i całe zamieszanie.
Przygoda zaczęła się od implementacji STL’owej, bo najłatwiej i najszybciej. Niestety spoj nie daje za wygraną i stale zwraca SIGSEGV. Program sprawdzałem debuggerem w Visual Studio i dla różnych danych nie wyrzucił mi nigdzie błędów (może raz out of range, ale dałem 500 000 punktów w generatorze a nie 50000 jak jest max w tym zadaniu).
Potem przepisałem to na zwykłe tablice [Implementacja własna] , tutaj zaczęła się seria WA. Testowałem jakoś tam, ale ręcznie trochę średnio takie coś sprawdzać, a magicznej skrzynki odpowiadającej na pytanie Dobrze/Źle nie posiadam.
Po kilkunastu nieudanych próbach poszukałem gotowca w necie i dołożyłem tam tylko zapamiętywanie pozycji punktów w sposób najszybszy i najbrzydszy z możliwych, ale i tak mamy WA.
Jak ktoś byłby tak miły i wrzucił jakiś teścik na którym to się wykłada, albo świeższym niż moje okiem zerknął w ten kod [implementacja własna] to będę wdzięczny.