1105 Culoar

[•andrei.12]

Aici puteți discuta despre problema Culoar.

[•Florian]

Cum se rezolva ? 

[•vladii]

Rezolvarea mea in N^3:
Distanta intre doua drepte paralele (daca stim panta si un punct de pe ele) este:
d = |A * x0 + B * y0 + C| / sqrt(A*A + B*B);
unde Ax + By + C = 0 este ecuatia uneia dintre drepte si (x0, y0) un punct de pe cealalta dreapta.
Cu niste mici modificari, ajungem la:
d = |m * c1 - c2| / sqrt(m*m + 1);
unde m = panta dreptelor si c1 = x0 - x1, c2 = y0 - y1 (coordonatele punctelor de pe cele doua drepte).
Am luat acum o functie:
f(m) = |m * c1 - c2| / sqrt(m*m + 1)
si am incercat sa ii gasesc monotonia. f(m) > 0 oricare ar fi m (pentru ca f(m) reprezinta defapt o distanta), deci daca f(m) ^ 2 este monotona pe un anumit interval, si f(m) este. Deci am derivat pe f(m) ^ 2 si am aflat radacinile derivatei: sa le notam cu R1 si R2. Ceea ce inseamna ca in punctele R1 si R2 este posibil ca functia sa isi schimbe monotonia (adica sa avem un maxim local sau minim local).
Deci un prim pas in algoritm consta in alegerea tuturor perechilor de puncte (i, j), determinarea radacinilor derivatei functiei f^2 (radacinile reprezinta defapt niste PANTE) si apoi vedeam in O(N) daca intre dreptele de panta R1 si R2 care trec prin punctele i si j exista vreun alt punct. Daca nu, era o asezare valida, calculam distanta intre aceste doua drepte si o comparam cu solutia.
Acum sa zicem ca avem doua drepte de panta m care trec prin doua puncte i si j. Daca rotim aceste drepte (adica marim sau scadem panta), evident vom forma intervale compacte (pentru panta). Ceea ce inseamna ca f(m) poate fi maxim doar daca dreapta care trece prin i mai trece si printr-un alt punct p, sau daca dreapta care trece prin j mai trece prin alt punct k, sau poate fi maxim intr-un punct oarecare dintre k si p, dar acest punct poate forma ori panta R1, ori R2, ceea ce noi am calculat deja .
Deci folosind aceasta observatie, luam toate perechile de puncte (i, j) astfel incit o dreapta sa treaca SI prin punctul i SI prin punctul j, si calculam in O(N) dreptele de aceeasi panta ca dreapta (i, j) si vedem pentru care dintre aceste drepte nu exista niciun punct intre dreapta (i, j) si ele, apoi calculam distanta si comparam cu solutia.

Cam asta este rezolvarea mea, in N^3 (sper ca nu am gresit cu nimic la calcule sau rationament), si solutia implementata pe ideea asta a luat 50p , cu TLE pe restul de teste. Partea mai nasoala este ca daca sar peste prima parte a algoritmului (adica nu mai calculez radacinile derivatei) si fac doar a doua parte, desi NU MERGE pe al 2lea exemplu din enunt, tot 50 de pcte ia .

Sunt curios si eu cum se rezolva problema (N^2, N^2 * logN ?).

Bafta!
Vlad.

[•Oancea.Catalin]

Problema asta a fost data la clasa a X-a? 

[•SpiderMan]

Clasele X - XIII si Open.

[•MciprianM]

Poate cineva sa detalieze cineva solutia la problema asta, va rog, ca eu nu ma prind? ( Sunt foarte slab la capitolul asta )
L.E.: Mai exact m-ar interesa cum aflam cel mai apropiat punct de fiecare dintre cele n^2 drepte. M-am gandit la o sortare a punctelor dupa inaltime, ca mai apoi sa putem cauta binar(si mai apoi cu o optimizare in O(1)) punctul cu inaltimea cea mai mica fata de o dreapta data, dar functia distanta intre o dreapta si un punct nu pastreaza ordinea daca schimbam dreapta.

[•S7012MY]

Si eu incerc sa rezolv problema dar nu inteleg solutia (

[•wefgef]

Solutia la aceasta problema nu era completa. Am mai adaugat putin, sper sa va ajute mai mult acum.

Dintre cei care au luat 100, daca vrea cineva sa detalieze solutia in articol este invitat sa o faca.