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.