067 Triang

[ditzone]

E un articol pe info.devnet despre hash-uri, te poti documenta acolo :
http://info.devnet.ro/articole.php?page=art&art=27

[•filipb]

Scrie de mana cautarea binara. Daca la compare_points ai comparat corect numerele reale ( adica x == y <=> |x-y| < EPS ) atunci nu are de la ce sa fie, decat de la functia care iti returneaza cel de-al treilea varf ( al triunghiului echilateral ) pentru perechea de puncte de coordonate (i,j). Vezi k pentru o pereche (i,j) sunt intotdeauna 2 puncte care indeplinesc proprietatea cu triunghiul echilateral!

[•Coty]

@ditzone: mersi, am sa-l studiez maine, azi am lucrat de la 9AM si... se cere o pauza
@filipb: am facut asa(am cautat un exemplu de functie compare_int si am convertit-o la compare_points):

Cod:

#define EPS 0.001
int compare_points(const void *a,const void *b) // for qsort & bsearch
{
	float* arg11=(float*)a;
	float* arg12=(float*)a+sizeof(float);
	float* arg21=(float*)b;
	float* arg22=(float*)b+sizeof(float);
	if(*arg11<*arg21 || (abs(*arg11-*arg21)<EPS && *arg12<*arg22))return -1;
	if(abs(*arg11-*arg21)<EPS && abs(*arg12-*arg22)<EPS)return 0;
	return 1;
}

apoi, pentru perechea (i,j) fac asa: who1 va fi punctul a[j] rotit in jurul lui a de i cu 60 de grade (bine, un pointer, pe care il trimit functiei) si who2 punctul a de i  rotit in jurul lui a[j] (echivalent cu a[j] rotit 300 grade). deci verific pentru doua puncte, daca am inteles bine la ce te refereai...
si am corectat apelul:

Cod:

			ans2=bsearch(who2,a+j,n-j+1,sizeof(punct),compare_points)

si acum imi da exemplul lor  si pentru 4 puncte si pentru 5 puncte, dar iau WA pe 7 teste si TLE pe celelalte... de la ce sa fie?!?

[•xtreme]

Salut, e normal sa iau 10 TLE-uri cu o solutie de complexitate O(N^2 logN)?Sau solutia mea e gresita?La problema aceeasta se poate lua 100 de puncte cu o solutie de complexitate O(N^2 logN)?

[•wefgef]

Din cate stiu eu se poate lua 100 cu O(N^2 log N).

[•robigi]

imi puteti da si mie un pont va rog asupra aflarii coordonatelor celui de-al treilea varf al unui triunghi echilateral cand ai coordonatele celorlalte 2?

[•freak93]

Prima metoda ar fi sa calculezi mediatoarea(x si y al dreptei).A doua si dupa pararea mea mai simpla de inteles este cea folosind numere complexe(asta daca ai cunostinte despre ele):
Ai acolo o teorema: Un triunghi e echilateral daca numerele complexe cu afixele A,B,C(ABC fiind triunghiul in ordine trigonometrica) satisfac urmatoarea relatie:
a+eps*b+eps*eps*c=0 unde eps=cos 60+isin60;

Stiind a si b,  c poate fi:
1) -a*eps-b*eps*eps sau
2) -b*eps-a*eps*eps(considerand triunghiul in ordine invers trigonometrica).

Sper sa te ajute

[•CezarMocan]

Prima metoda mai detaliata ar suna cam asa:
Notam cu L lungimea laturii triunghiului echilateral, cu M mijlocul segmentului pe care tu il ai. Se stie ca inaltimea intr-un triunghi echilateral este egala cu L * sqrt(3) / 2. Afli ecuatia mediatoarei segmentului tau (dreapta care trece prin M si e perpendiculara pe segment) si in momentul asta te intereseaza un punct care se afla la distanta L * sqrt(3) / 2 de M (1) si satisface ecuatia mediatoarei (2).
Scriind relatiile (1) si (2) obtii un sistem de 2 ecuatii cu 2 necunoscute (coordonatele punctului). Din cauza ca sistemul o sa se reduca la o ecuatie de gradul II o sa obtii 2 solutii (varful poate fi de ambele parti ale segmentului). Sper ca am fost suficient de explicit.

[•wefgef]

http://en.wikipedia.org/wiki/Rotation_matrix

[•robigi]

Multumesc mult pentru tot.

Prima metoda o cunosteam si eu, dar mi sa parut putin cam ineficienta.

[•R.A.R]

Am incercat sa o rezolv folosind o tabela de dispersie insa primeam Signal11 ,dupa ceva modificari am ajuns sa primesc WA.
Am modificat sursa pana am ajuns la rezolvarea in O(N^3) dar si asa primesc WA la teste.Nu stiu daca e gresita formula sau e o problema de precizie(desi nu cred ).
Formula pt a determina coordonatele celui de-al 3-lea puct este :  

Cod:

x = (-x1+y1*s3+x2+y2*s3)/2;
y = (-y1-x1*s3-x2*s3+y2)/2; //cu s3 am notat radical din 3.

?(am folosit numere complexe)

[•ctlin04]

Rog un admin sa se uite daca este in regula evaluatorul problemei, iau TLE cu complexitatea O( N^2logN ), chiar de interes am retrimis o sursa ce lua 100 cu timpi sub 200 ms si poftim rezultatul:
http://infoarena.ro/job_detail/699907
http://infoarena.ro/job_detail/770115
aceeasi sursa ruleaza mult mai lent, chiar ia TLE pe un test si asta nu mi se pare normal 
Aceeasi problema este si la http://infoarena.ro/problema/curcubeu.

[•dushmi]

Rog un admin sa se uite daca este in regula evaluatorul problemei, iau TLE cu complexitatea O( N^2logN ), chiar de interes am retrimis o sursa ce lua 100 cu timpi sub 200 ms si poftim rezultatul:
http://infoarena.ro/job_detail/699907
http://infoarena.ro/job_detail/770115
aceeasi sursa ruleaza mult mai lent, chiar ia TLE pe un test si asta nu mi se pare normal  
Aceeasi problema este si la http://infoarena.ro/problema/curcubeu.

Done, am modificat eu limitele de timp (la ambele). Uneori evaluatorul merge mai prost . De acum incolo te rog sa postezi astfel de probleme aici.

[•dutzul]

eu am alta idee care nustiu cum se face am tot incercat pe foaie da nu merge:
deci iau 2 puncte ,calculez panta si incerc sa rotesc dreapta cu 90 de grade . astfel pot afla ecuatia dreptei.
stiu ca se poate si altcumva dar eu sunt curios cum se roteste o dreapta la care i cunosti panta please help.
mersi anticipat

[•SebiSebi]

Stii panta dreptrei (si neaparat un punct A care apartine dreptei, eventual mijlocul segmentului). Ai formula care spune ca daca doua drepte sunt perpendiculare atunci produsul pantelor este -1, deci afli panta noii drepte. Cunosti panta si un punct <=> ecuatia dreptei este d : y-yA=md(x-xA) .
Insa abordarea este greoaie si se poate pierde precizie . Daca ai notiuni de baza despre numere complexe , stii condititia ca un triunghi sa fie echilateral si gradul de dificultate al problemei se reduce foarte mult.

[•dutzul]

hmm o sa citesc despre numere complexe sti vrun articol pe net bun? (pe romana) oricum eu inca is curios cum rotesti o dreapta cu o panta anume(nu numa sa o rotesti cu 90*) sa zicem ca cu 45* .
mersi.

[•SebiSebi]

Uite aici un articol despre numere complexe : http://bacmd.com/attachments/186_numere_complexe.pdf .
Este destul de bun din cate am citit eu. Cat despre a doua intrebare... Stii ca tg a = m unde m=unghiul dintre axa OX si dreapta. Aflii unghiul a, si aduni/ scazi unghiul de rotatie, deci stii noua panta (trebuie sa tratezi cazurile particulare = atunci cand nu exista tangenta, si sa vezi in ce cadran(e) se afla segmentul.

[•mathboy]

In principiu e bine sa te gandesti la un numar complex (de forma A + Bi) ca fiind un vector care porneste din origine cu coordonatele A(pe axa OX) si B(pe axa OY) .
Geometric, inmultirea cu i a unui vector "stand" pe o axa reprezinta de fapt rotirea sa cu 90 de grade (adica pe axa urmatoare din stanga), de unde si faptul ca i^2 = -1 ( 1 * i * i = -1).
Nu am vazut asta in articolul dat de George si m-am gandit ca ar prinde bine cuiva.

[•S7012MY]

Cred ca ar merge marita putin limita de timp