Solved
Closest_pair_problem I'll vote 500 points for you
Posted on 2006-04-19
{i wrote this based on Sedgewick'Book.,i feel very difficult, i understood algorithms, but this program can't run. Please help me as soon as possible, My experts, my brother, I'll vote 500 points for you, all of you.. after i finish "divide and conquer", " i will write this with algorithm:"a plane sweep, and sorry for bothering you."}
{ because i'm 14 years old pupil, please explain clearly, especially, this program seems to be correct but it can't run.}
{and i'd like to know how to use time function in pascal to display time of algorithm, when i use a large set of points, thank you}
program closest_pair; { divide and conquer}
uses crt,dos,overlay;
type
point = record
x: real;
y: real;
end;
link = ^node;
node = record
p: point;
next: link;
end;
var
keeptrack: link; { i'll use it to keep track of my list}
list,head: link; {i'll use list to input a set of points}
first: link;
minresult: real;
closest1,closest2: point; {current closest pair, they can be updated}
sortx: boolean; {sortx = false -> sort y}
n,v: integer; {n points}
function merge(list1,list2 :link) : link;
var list12: link;
addlist :boolean;
begin
list12:= keeptrack ; {it seems to be unlimited loop, really difficult or i have a wrong list that declares in the main program }
repeat
if sortx = true then addlist:= list1^.p.x < list2^.p.x
else addlist:= list1^.p.y < list2^.p.y ;
if addlist then begin list12^.next := list1; list12:= list1; list1 := list1^.next end
else begin list12^.next := list2; list12:=list2; list2 := list2^.next end
until list12 = keeptrack;
merge := keeptrack^.next;
keeptrack^.next := keeptrack;
end;
procedure check(p1,p2: point); { it's easy, i got it}
var distance : real;
begin
if (p1.y <> keeptrack^.p.y) and (p2.y<> keeptrack^.p.y) then
begin distance := sqrt((p1.x -p2.x)*(p1.x -p2.x) + (p1.y -p2.y)*(p1.y - p2.y));
if distance < minresult then
begin minresult:= distance;
closest1:= p1;
closest2:= p2;
end;
end;
end;
function sort(c: link; n: integer):link;
var a,b: link;
i: integer;
middle: real;
p1,p2,p3,p4: point;
begin
if c^.next = keeptrack then sort:= c else
begin a := c;
for i:= 2 to (n div 2) do c:= c^.next;
b:= c^.next;
c^.next := keeptrack;
if sortx = false then middle := b^.p.x;
c := merge(sort(a, n div 2), sort(b,n-(n div 2)));
sort := c;
if sortx = false then
begin
a:= c; p1:=keeptrack^.p; p2:=keeptrack^.p; p3:= keeptrack^.p; p4:= keeptrack^.p;
repeat
if abs(a^.p.x - middle) < minresult then
begin check(a^.p,p1);
check(a^.p,p2);
check(a^.p,p3);
check(a^.p,p4);
p1:=p2; p2:=p3; p3:=p4; p4:=a^.p;
end;
a:= a^.next;
until a=keeptrack ;
end;
end;
end;
begin { please check this for me,do i have s mistakes}
new(keeptrack);
keeptrack^.next:=keeptrack;
keeptrack^.p.x:= maxint;
keeptrack^.p.y:= maxint;
writeln('how many points are there on the plane: ????');
readln(n);
list := nil;
for v:=1 to n do begin
new(first);
first^.p.x := random(1000);
first^.p.y := random(1000);
first^.next := list;
list := first;
end;
new(head); head^.next:= list;
minresult := maxint;
sortx:= true; head^.next:=sort(head^.next,n);
sortx:= false; head^.next:= sort(head^.next,n);
writeln(closest1.x); { the problem is not important anymore}
readln;
end.