046 Cele mai apropiate puncte din plan

[•Marius]

Aici puteţi discuta despre problema Cele mai apropiate puncte din plan.

[•Bogdan_tmm]

Cred ca testele nu sunt chiar foarte bune.
Cu solutia gresita am reusit sa scot cel mai bun timp de pana acum.
Iata un exemplu:

[•Marius]

Cred ca testele nu sunt chiar foarte bune.
Cu solutia gresita am reusit sa scot cel mai bun timp de pana acum.
Iata un exemplu: ...

Nu am înţeles ce faci. Reformulează, te rog.

[•Bogdan_tmm]

Sa zicem ca punctul 9 va fi mijlocul cand se revine din apeluri.
Acum incerc sa caut distanta minima intre punctele de indici
2 3 4 ... 9...15 16, deci nu o sa gasesc minimul,acesta fiind intre punctul 1 si 17.
Distantele pe verticala intre punctele 1-2 2-3 ... 7-8 este MARE.La fel si distanta intre 10-11 11-12 ...16-17 iar mijlocul(punctul 9) se afla la o distanta destul de MARE de (sa zicem) punctul 10.

Cod:

	for(i=mj;i>=st&&i>=mj-7&&a[mj].x-a[i].x<=MIN;i--);
	for(j=mj;j<=dr&&j<=mj+7&&a[j].x-a[mj].x<=MIN;j++);
	for(i1=i+1;i1<j;i1++)
		for(j1=i1+1;j1<=j;j1++)
			Min=min(Min,dst(i1,j1));

[•Bit_Master]

Nu putem mai simlu sa avem doua siruri, unul sortat dupa abscisa si celalalt dupa ordonata? Il impartim in jumatati pe cel sortat dupa abscisa si cand revenim dintr-o recursivitate (dintr-o impartire), cautam in sirul sortat dupa ordonata toate punctele care sunt la distanta maxim S de locul de impartire si le punem in sirul Y. Am avea tot complexitate N * log₂n. log₂n submultimi care le injumatatim si pentru care vom face N pasi sa construim sirul Y si apoi inca N pasi sa parcurgem sirul Y. Deci O(2 * N * log₂n) = O(N * log₂n).

_____________________________________________

Am mai reparat ceva, dar tot nu suficient. Puteti pune si voi teste mai mici? Nici nu stiu de ce mai sunt publice daca pe testul 1 ai 1000 pct, pe testul 2 1000, pe 3 10000 etc... Nu poti face debug cu asa un test.

_____________________________________________

Si de ce n-ar fi inca 5 pcte de luat pt fiecare (6 in total)? Cele de pe dreapta de impartire n-ar fi comune?

[•zsee]

Imi poate spune cineva care e problema in sortarea in sursa asta? 
http://infoarena.ro/job_detail/502112

Sunt sigur ca acolo e problema ca cu shellsort imi iese, dar nu intra in timp la ultimele teste... http://infoarena.ro/job_detail/502111  si combinand cele doua tipuri de sortare iau 100 de pct... http://infoarena.ro/job_detail/502113

[•BuRN]

in sursa http://infoarena.ro/job_detail/552639?action=view-source cazul in care minimul este in partea stanga sau dreapta nu l-am tratat ... doar cel in care un punct este in stanga si unul in dreapta dreptei "D" .
 Am luat 100p. , inseamna ca nu sunt teste cu minimul in stanga/dreapta ?

[•batista]

Salut!
Am vazut surse care iau 100 chiar daca nu sunt corecte.
Cred ca ar trebui pus si testul:
9
0 0
0 3
0 6
0 9
0 12
0 15
0 18
0 21
0 1

Multe surse care iau intotdeauna cele mai apropiate 8 puncte sortate dupa x iau 100 de puncte!

[•moraru.c]

am si eu o intrebare...acest algoritm se poate executa in paralel folosind functii din libraria OpenMP??

[•Bogdan_tmm]

Nu stiu exact in ce consta acea librarie, insa cu siguranta poate fi paralelizat deoarece fiecare subproblema poate fi rezolvata independent...

[•retrograd]

Salut! Am luat 100 de puncte cu un algoritm care nu are complexitatea nici pe departe NlogN. Cred ca testele ar trebui revizuite, desi realizez ca e destul de greu sa se combata asa o solutie...

Codul este f simplu. Practic indexez punctele dupa abscisa si ordonata, si ma opresc cand diferenta de abscise/ordonate depaseste dmin:

http://www.infoarena.ro/job_detail/1453063?action=view-source

Se pare ca nu va trebui sa implementez solutia D&C pana la urma... 

[•AlexandruValeanu]

Se pare că va trebui să implementezi "solutia D&C" dacă vrei să înveți ceva.

P.S. Poți reface chiar tu testele.

[•retrograd]

Se pare că va trebui să implementezi "solutia D&C" dacă vrei să înveți ceva.

P.S. Poți reface chiar tu testele.

Cred ca nu e mare lucru sa se mai adauge doua teste, unul in care toate punctele sunt pe aceeasi verticala si apoi pe aceeasi orizontala. Zic si eu

[•RazvanR104]

Am o dilema legata de solutiile postate pentru 100 de puncte.

Linia 39 @ http://www.infoarena.ro/job_detail/383250?action=view-source (are echivalent si in sursa cealalta, de complexitate N * log^2(N))

Cod:

for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best)

Conditia nu ar fi, de fapt:

Cod:

if (1ll * (Y[i].second - X[mid].first) * (Y[i].second - X[mid].first) <= best)

Din cate inteleg, best fiind cea mai mica distanta la patrat, ar trebui sa alegem punctele a caror distanta patrata pe orizontala fata linia verticala este mai mica sau egala cu best.
Avand conditia curenta (cea din sursele oficiale) se mai pastreaza invariantul verificarii a doar 8 puncte consecutive?

Sper sa ma ajute cineva cu o clarificare.
Multumesc mult!

LE: sursa de 100p care foloseste conditia cu distanta patrata: http://www.infoarena.ro/job_detail/1803161?action=view-source

[•Bogdanisar]

Din cate inteleg, best fiind cea mai mica distanta la patrat, ar trebui sa alegem punctele a caror distanta patrata pe orizontala fata linia verticala este mai mica sau egala cu best.
Avand conditia curenta (cea din sursele oficiale) se mai pastreaza invariantul verificarii a doar 8 puncte consecutive?

Ai dreptate. Ar trebui sa se aleaga punctele a caror distanta la patrat fata de linia verticala este mai mica sau egala cu best, insa algoritmul de 100p postat ramane corect. El doar face un numar nenecesar de pasi, considerand si unele puncte prea indepartate de linia verticala ca sa se poata obtina cu ele o noua distanta minima.
Banuiesc ca a fost doar o scapare din vedere cand s-a scris sursa. 

[•RazvanR104]

^ Nu cred ca ramane corect. Ambele surse verifica cate 8 puncte in ordine. Avand distanta setata mai mare, ar trebui verificate mai mult de 8 puncte (nu se mai respecta supozitia din care s-a dedus numarul de 8 puncte).

[•Bogdanisar]

De fapt, ai dreptate. Algoritmul poate da un raspuns gresit daca se scapa din vedere detaliul cu distanta la patrat.
Am reusit sa fac un test care da gresit pentru sursa oficiala de 100 de puncte

Input:

Cod:

18
-9000 900
-8000 900
-7000 900
-6000 900
-5000 900
-4000 900
-3000 900
-2000 900
0 800
1 1000
9000 900
8000 900
7000 900
6000 900
5000 900
4000 900
3000 900
2000 900

Output corect:

Cod:

200.002500

Output-ul sursei oficiale:

Cod:

1000.000000

[•andreeasin]

Am trimis din greseala sursa aceasta