|
|
вернуться в форумWhats wrong with my algorithm or code? First i calculate the degree between wally house and every friend by procedure ATG and then sort friends by their degree... Type Point =record x,y,d :real; ID :Integer; end; Var a :array[0..1000] of point; n,i :integer; function partition(first,last:integer):integer; Var t :point; i,j :integer; x :real; begin i:=first-1; j:=last+1; x:=a[first].d; while true do begin repeat inc(i); until a[i].d<=x; repeat dec(j); until a[j].d>=x; if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end else begin partition:=j; exit; end; end; end; Procedure qsort(first,last:integer); Var w :integer; begin if first<last then begin w:=partition(first,last); qsort(first,w); qsort(w+1,last); end; end; Function ATG(x:integer):real; Var dx,dy,k :real; begin dx:=a[x].x-a[0].x; dy:=a[x].y-a[0].y; if dx=0 then k:=90 else k:=arctan(dy/dx)/pi*180; if (k<0) or ((k=0) and (dx<0)) then k:=k+180; if dy<0 then k:=k+180; atg:=k; end; begin readln(a[0].x,a[0].y); readln(n); for i:=1 to n do begin readln(a[i].x,a[i].y,a[i].ID); a[i].d:=ATG(i); end; qsort(1,n); writeln(0); for i:=1 to n do writeln(a[i].Id); writeln(0); end. Wally's house may be at center, so, your program doesn't work (-) > First i calculate the degree between wally house and every friend by > procedure ATG and then sort friends by their degree... > > Type > Point =record > x,y,d :real; > ID :Integer; > end; > Var > a :array[0..1000] of point; > n,i :integer; > > function partition(first,last:integer):integer; > Var > t :point; > i,j :integer; > x :real; > begin > i:=first-1; > j:=last+1; > x:=a[first].d; > while true do > begin > repeat inc(i); > until a[i].d<=x; > repeat dec(j); > until a[j].d>=x; > if i<j then begin > t:=a[i]; a[i]:=a[j]; a[j]:=t; end > else begin > partition:=j; exit; end; > end; > end; > > Procedure qsort(first,last:integer); > Var > w :integer; > begin > if first<last then > begin > w:=partition(first,last); > qsort(first,w); > qsort(w+1,last); > end; > end; > > Function ATG(x:integer):real; > Var > dx,dy,k :real; > begin > dx:=a[x].x-a[0].x; > dy:=a[x].y-a[0].y; > if dx=0 then > k:=90 > else > k:=arctan(dy/dx)/pi*180; > if (k<0) or ((k=0) and (dx<0)) then k:=k+180; > if dy<0 then k:=k+180; > atg:=k; > end; > > begin > readln(a[0].x,a[0].y); > readln(n); > for i:=1 to n do > begin > readln(a[i].x,a[i].y,a[i].ID); > a[i].d:=ATG(i); > end; > qsort(1,n); > writeln(0); > for i:=1 to n do > writeln(a[i].Id); > writeln(0); > end. > but it works... i calculate degree in range 0..360 may you tell me a test???? See(+) Think of the following Input: 0 0 3 1 0 1 0 -1 2 1 -1 3 Output: 0 2 3 1 0 Luck! Hey Special thanks at last i correct my solution here: if there where two friend with house number i and i+1 which a[i+1]-a[i]>180 (it is obvious that there will be at last just one of this type) then path be i+1-i+2-...-n-...-1-2-3-...-i Thanks a lit for another AC :) yours Aidin_n7@hotmail.com |
|
|