067 Triang

[•domino]

Aici puteţi discuta despre problema Triang.

[•vladcyb1]

Am o nedumerire la problema asta.
Pe exemplu:
iau punctele :
(0 0) si (4 0) obtin un al treilea varf punctul (2 3.464101651377)
iau punctele
(4,0) si (2 3.4641016) obtin un al treilea varf (1.31*10^-8 7.568*10^-9)

ambele puncte obtinute sunt foarte aproape de cele din fisierul de intrare, dar sunt diferite de la o anume zecimala in colo.
Daca e sa iau eroarea de 10^-3 cum zice in enunt imi da 2 triunghiuri, daca micsorez eroare imi da 0 triunghiuri. In enunt zice ca raspunsul este 1.

Cum trebuie sa fac ca sa o scot la capat?

[•domino]

Am o nedumerire la problema asta.
Pe exemplu:
iau punctele :
(0 0) si (4 0) obtin un al treilea varf punctul (2 3.464101651377)
iau punctele
(4,0) si (2 3.4641016) obtin un al treilea varf (1.31*10^-8 7.568*10^-9)

ambele puncte obtinute sunt foarte aproape de cele din fisierul de intrare, dar sunt diferite de la o anume zecimala in colo.
Daca e sa iau eroarea de 10^-3 cum zice in enunt imi da 2 triunghiuri, daca micsorez eroare imi da 0 triunghiuri. In enunt zice ca raspunsul este 1.

Cum trebuie sa fac ca sa o scot la capat?

Incearca ca atunci cand calculezi al treilea varf sa faci calculele astfel incat sa pierzi cat mai putina precizie. Eroarea de 10^-3 ar trebui sa fie de ajuns.

[•vladcyb1]

Hai ca am reusit sa trec de faza cu precizia, dar iau 40 de puncte restul TLE. Am facut double hashingul lui Patrascu, dar cred ca am ales valorile gresite pt dispersie. Imi poti zice si mie ce valori trebuie sa folosesc la dispersia numerelor reale?
folosesc functia h(x)=[{x*a}*M]
a=numar real (0,1)
M=dimensiunea tabelei

[•bogdan2412]

Nu stiu ce sa-ti spun despre hash, dar iti recomand o solutie mult mai scurta si mai simpla in N^2 log N folosind nishte rotatii si o cautare binara.

[•vladcyb1]

Am facut cu cautare binara si iau 70 de puncte. Am cautat binar pe x si cand l-am gasit am cautat pe y binar intre punctele care au abscisa x. Se poate mai repede ca sa iau 100?  

[•bogdan2412]

Nu, asa am facut si eu cautarea binara. Incearca sa mai faci optimizari si, in caz ca nu faci asta deja, foloseste cautarea binara din articolul http://info.devnet.ro/articole.php?page=art&art=22

[•vladcyb1]

Am implementat cautrea binara din aricol si tot 70 de puncte iau. Nu mai am ce sa optimizez, pur si simplu iau oricare 2 puncte, le rotesc, obtin al treilea punct si dupa aia caut binar. Nu fac nici o operatie in plus. Eu cred ca problema a fost data pt hash, asa ca revin si intreb din nou, ce valori trebuie sa aleg pt dispersie?  

[vladut.forum]

hmm daca iei TLE, s-ar putea sa fie din cauza cautarii binare.. pt unele cazuri nu se mai termina de blocat deoarece se blocheaza
da si mie sa vad secventa de cautare binara....

[•vladcyb1]

Il caut pe (xt,yt) in vectorul L care are doua campuri l.x si l.y, e vectorul cu puncte sortat.

Cod:

procedure binaryx;
var step,i:integer;
begin
step:=1;
while step<n do step:=(step shl 1);
i:=0;
 while step>0 do
  begin
  if(step+i<=n)and((l[step+i].x<xt)or(compar(l[step+i].x,xt))) then i:=i+step;
  step:=step shr 1;
  end;
 if compar(xt,l[i].x) then pz:=i
                      else pz:=1600;

end;

procedure binaryy(li,lo:integer);
var step,i:integer;
begin
step:=1;
while step<lo do step:=step shl 1;
i:=li-1;
 while step>0 do
  begin
  if (i+step<=lo)and((l[i+step].y<yt)or(compar(l[step+i].y,yt))) then i:=i+step;
  step:=step shr 1;
  end;
 if compar(l[i].y,yt) then find:=true
                      else find:=false;
 end;
 

procedure cauta(x,y:real);
begin
xt:=x; yt:=y;
binaryx(1,n);
if pz<>1600 then
 begin
  binaryy(pz-v[pz]+1,pz);
  if find then inc(rez);
  end;
  
end;

Functia compar da true daca coordonatele sunt egale.

[•filipb]

Si eu tot binar am cautat si tot 70 am luat, pe ultimele 3 teste TLE... Cel de-al treilea punct il gaseam insa altfel: din mijlocul segmentului celor doua puncte curente duceam o perpendiculara de lungime l * sqrt(3) / 2 in ambele directii posibile si aflam astfel coordonatele celui de-al treilea punct. Un algoritm O(N^2 log N) zic ca ar trebui sa se incadreze fara probleme in 1 secunda... dar la mine nu se incadreaza pentru ca am prea multe calcule consumatoare de timp...
   Sincer sa fiu, eu nu as incerca cu hash aici, mi se pare prea mica probabilitatea sa nu greseasca ( indiferent de cheia pe care o alegi )...

                                   bubbleSORT

[•vladcyb1]

Am facut si hashu-l ala ala al lui Knuth pt numere reale dar am luat 40 p . Restul TLE !!!!  

[u-92]

nu m-am uitat peste codul tau.. dar eu am cautat binar doar pe x, pe y am mers in stanga si in dreapta pana nu mai corespundeau coordonatele..
i = 1 to n-2
j = i+1 to n-1
cauta_binar(j+1, N);
cam asa.. nu prea stiu ce calcule consumatoare de timp ai facut.. eu am scos o ecuatie de gradul 2 de unde aflam cele 2 puncte

[•vladcyb1]

Si ai luat 100 asa? In mod normal daca am cautat binar si pe Y mie ar trebui sa-mi mearga mai repede.  

[u-92]

da.. am luat 100

[•vladcyb1]

asa iau 60. Problema asta kiar ma enerveaza! Ce optimizari ati mai facut pe acolo? Ati sortat cu quick-sort, nu? Deci iau oricare 2 puncte le rotesc in o(1) si caut binar atat.    

[u-92]

eu am sortat cu bubble sort cred ca ai o greseala ceva in algoritm.. iei TLE sau WA?

[•vladcyb1]

TLE !

[cristi8]

eu am facut cu hash si am luat 100..
cat despre functia de dispersie, m-am uitat acum pe sursa si   ce sa vad..

Cod:

#define EPS 0.001
#define HSIZE 30007
int hf(double dst)
{
  int ret;
  ret = dst+EPS;
  return ret%HSIZE;
}

..chiar nu stiu de ce am asa ceva in sursa..  

oricum, am facut niste optimizari pe-acolo.. adica nu stergeam hashul cand treceam la alt "punct sursa".. doar ignoram ce era in el (mai castigam viteza)

..tu ce algoritm folosesti ? cum calculezi solutia ?

[•vladcyb1]

iau oricare 2 puncte, il calculez pe al treilea (care de fapt sunt doua puncte: unul pe stanga si unul pe dreapta) si acuma caut in hash.
 Hashul meu e de fapt double hash si functioneaza asa:
hash 1 are hsize=1013 si are a=(sqrt(5)-1)/2
hash 2 are hsize=2411 si are a=(sqrt(19)-2)/3

functia de dispersie este asta: cheie:=abs(trunc(frac(a*(x+y))*hsize));

Inserarea o fac astfel: pt fiecare punc calculez cele doua chei pt ca am doua formule si inserez punctul la cheia care are cele mai putine elemente introduse pana atunci.
Cautarea o fac in ambele tabele de hash dupa cheile obtinute prin formula.

NU folosesc pointeri.

Al treilea punc il calculez in O(1) cu rotire
Cam asta e tot cu hash.

Mai am si varianta cu cautare binara care are punctele sortate dupa x si la x egal sortate dupa y si pt fiecare punct obtinut din rotire caut binar dupa x si dupa aia intre punctele ce au acelasi x caut binar pe y.

Varianta cu double hash ia 60 de puncte si cea cu cautare binara ia 70 de puncte.
S-ar putea sa fie si din cauza ca scriu in Pascal

[•cyron]

se ia 100 si cu pascal    

[cristi8]

ma.. eu uite cum fac.. mai intai calculez d[][] (distanta intre oricare 2 puncte).. o(n^2)
dupa aia.. uite un pseudocod:

Cod:

pt i de la 1 la n-1
  pt j de la i+1 la n
    sol <- sol + hsearch(d[i][j], i, j)
    hadd(d[i][j], i, j);

unde hadd() adauga in hash ca "de la SURSA i, exista o distanta d[j] pana la punctul j"
si hsearch() cauta in hash "cate puncte exista la distanta d[j] de SURSA i si la distanta d[j] de punctul j"

fac hashul dupa distanta, si in fiecare element din hash retin distanta, punctul SURSA, si celalalt punct.

[•Coty]

Cod:

	NR=0;	
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++)
		{
			who1=malloc(sizeof(punct));
			who2=malloc(sizeof(punct));
			ans1=malloc(sizeof(punct));
			ans2=malloc(sizeof(punct));
			*who1=rotate60(a[i],a[j]); // rotate60 roteste pe a[j] in jurul lui a[i] cu 60 de grade in sens trigonometric
			ans1=bsearch(who1,a,n,sizeof(punct),compare_points);
			if(ans1!=NULL)++NR;
			*who2=rotate60(a[j],a[i]);
			ans2=bsearch(who2,a,n,sizeof(punct),compare_points);
			if(ans2!=NULL)++NR;
		}

sunt qsortate inainte tot de functia din stdlib... si nu inteleg ce are  ma chinui la ea de vreo 2 ore (nu puneam malloc)... acum imi numara de mai multe ori triunghiurile... ziceti-mi va rog daca asta e bine si eventual care sunt indicii intre care trebuie sa ma plimb... si btw, are complexitatea n^2 log n dar iau 3 TLE... deci trebuie ceva mai bun

[•filipb]

Pentru o pereche de indici (i,j), i < j, cauti un k > j astfel incat punctele determinate de indicii (i,j,k) sa formeze un triunghi echilateral. Merge si mai bine de O(N^2 log N), in O(N^2), daca citeai mai sus, cu o tabela de hash dubla.

[•Coty]

...si daca si stiam ce e aia (ca de citit am citit) ma rog, mersi de indicatie!  btw, am modificat

Cod:

			ans1=bsearch(who1,a+j+1,n-j,sizeof(punct),compare_points);

nu ar trebui sa mearga?... ca nu vrea. ufff, o sa fac pana la urma cautarea binara de mana... si, de ce nu, un n^3, macar sa vad ca merge