10343. Taksówka na Manhattanie 2 [TAXIMAN2]

[knock_knock]

Witam. Sędzia daje błędną odpowiedź. Macie propozycje co do testów?
kod:

https://ideone.com/bzLis1

Co sądzicie o
in:
3
1 1
0 0
1 1
out:
2?

[narbej]

0?

[knock_knock]

W poleceniu mowa jest o najblizszych skrzyzowaniach, a dwa o tych samych wspolrzednych to to samo skrzyżowanie.

[witman]

2
-1000000000 1000000000
1000000000 -1000000000

Twój program daje wynik 2000000000

[narbej]

W poleceniu mowa jest o najblizszych skrzyzowaniach, a dwa o tych samych wspolrzednych to to samo skrzyżowanie.

Jaki wniosek wynika z powyższego?
Sprawdziłem, autor, Witold @witman tak dobrał testy aby takich nie było;-)

Przyznaję się, że nie sprawdzałem dokładnie ani twojego kodu, ani treści zadania. Taką odpowiedź podał mi mój AC program, ale mimo wszystko wolałem dodać znak zapytania [program podał tylko 0] ;-).

PS
Pozdrawiam autora

PS 2
dziwne, ale dla testów od 1 do 100…00 jest ok
np
2
-1 1
1 -1
ale dzisiaj już nie jestem w stanie tego analizować…

PS 3
wydaje mi się, że long long jest tu nadmiarem bezpieczeństwa. Sądzę, że int [do wczytywania] i unsignet [int 4294967295] do obliczeń jest tu wystarczający ale użycie pojemniejszego typu [long long] nie powinno wpływać na końcowy wynik.

EDIT
Do wczytania int wystarczy, ale do wyniku raczej jednak long long to minimum.

[knock_knock]

Serdecznie dziekuję za pomoc. Poprawiłem kod dla testu

2
-1000000000 1000000000
1000000000 -1000000000

Dodatkowo podjąłem walkę z

że long long jest tu nadmiarem bezpieczeństwa

jednak w kilku miejscach dochodzi do zgrzytu i potrzeba zmiennej, której pojemność jest +/- unsigned int . Dla świętego spokoju zostawiam longlongi, a potem je poprawię.
Kod w trochę ładniejszej i uproszczonej wersji dalej nie przechodzi z powodu błednej odpowiedzi:
https://ideone.com/WfMMC4

Chciałbym dodatkowo zapytać się o relację między scanf/printf a zmiennymi "lld". Czy w niej tkwi problem. Gdzieniegdzie widziałem propozycje użycia "I64d" zamiast "lld".

[mariusz193]

Problem leży w algorytmie, tak prosto się nie da. (a na maksymalną odległość da się prosto zrobić)
Co prawda, od początku nie miałem wątpliwości, jak również byłem przekonany, że wystarczą 4 skrzyżowania do wykazania błędu, ale już znalezienie dobrego przykładu zajęło mi trochę czasu

program + dane

[narbej]

Ja dodałbym do tego jeszcze kilka uwag:

1. Zmienne globalne są BEE
2. Oj nie tak, nie tak, panowie: long long int x[n],y[n]; to się nie tak robi.
3. Własny quick_sort? A przecież używasz STL <-- include `<algorithm>`
4. Podobnie absval, minimum, maximum.
5. Nazwa zmiennej powinna być samomówiąca do czego służy, np.: max_dx, maxDX, lub powinieneś użyć komentarza, opisującego znaczenie i przeznaczenie zmiennej.
6. Albo używaj konsekwentnie polskich nazw - lewa, prawa, srodek, albo angielskich, ale nie mieszanki i polskich i angielskich
7. pivot? not better middle or central, center ...
8. cytując mnie wyciąłeś "wydaje mi się, ..." oraz, że do wczytywania potrzebny jest typ signed - ale int wystarczy, natomiast do obliczeń musi być już pojemniejszy typ, ale możliwe, że unsigned int wystarcza.
9. Liczysz odległości [dist] trochę inaczej niż wydaje mi się, że można, ale i tak wartość twojej zmiennej mx=50000000000000, jest o wiele za duża. Moim zdaniem wystarczy 2000000000, a więc typ int.

[knock_knock]

Dziękuję za pomoc. Twój test całkowicie położył mój algorytm. Spróbuję wymyślić inną metodę i zmierzę się z tym zadaniem za jakiś czas

[knock_knock]

1. masz rację ;p
2. też mi się to nie podoba, ale wskazniki i rezerwowanie pamięci (o ile to masz na myśli) zaćmiło by mi i tak już dosyć trudne zadanie ;p
3. dzięki
4. dzięki dzięki, trochę zbyt samodzielnie ;p
5. 6. nie mam jeszcze opracowanych nazw, ale postaram się trzymać angielskich bo tak bardziej międzynarodowo wygląda kod ;p
6. [edit by narbej - edytor sam sobie liczy numery pkt wejdż w edycję i sam zobacz]
7. gdzieś oznaczone to było jakoś oś - ale nazwa też z ...y
8. wybacz wybiórcze cytaty
9. te wymiary to mój koszmar, bo gdy brałem dokładny to niekiedy dziwne liczby wyświetlał mi program.
10. jak zawsze mogę liczyć na Twoją pomoc dzięki i wrócę kiedy indziej z tym zadaniem (może już nawet nie na forum ;p)

[narbej]

AD 2
vector <pair <int, int> > pkt(n)

for (auto &i : pkt);  // auto c++ >= c++11
    cin >> i.first >> i.second;  // first == x; second == y

sort(pkt.begin(), pkt.end()); // sortowanie - domyślne niemalejąco

/// testowanie czy posortowane ;-)
for (auto i: pkt)
   cout << i.first << " " << i.second << endl;

[narbej]

TABLICE tworzyć
można też oczywiście z wykorzystaniem wskaźnika
int *tab = new ...

lub użyć tablicy statycznej:
int tab[2*100000][2]; /// (2 ≤ n ≤ 2*10^5)

lub użyć structury lub klasy
struct pkt {
int x, y;
}

[anon41185149]

Witam. Stwierdziłem że w tym zadaniu punkty mogą być najbliżej siebie w każdym miejscu układu więc zrobiłem program sprawdzający wszystkie możliwości.
Tu jest Kod
Niestety sędzia zwraca mi błędną odpowiedź. Mógłbym się spytać gdzie jest błąd?
Pozdrawiam.

[mariusz193]

a dyskusje powyżej przeczytałeś ? - oczywiście,że nie - nie zadawałbyś tego pytania

wystarczy prosty test, tylko 2 punkty:

2
 1000000000  1000000000
-1000000000 -1000000000

[anon41185149]

Ideone pokazywał błędny wynik. U mnie ten test przechodzi. Zmiana tablicy na long long int pomogła.
Niestety jest przekroczony limit czasu.

[narbej]

Ideone pokazywał błędny wynik. U mnie ten test przechodził.

Używałeś wcześniej u siebie long int?

Niestety jest przekroczony limit czas

Tak to jest niestety często, gdy porównuje się każdą[ego] z każdym[ą] …

W między czasie, proponuję Ci zapoznać się z 833. Dwumiany [BINOMS] oraz podanym tam wątkiem JZLICZ a potem jeszcze jednym linkiem dalej