Solved

Posted on 2006-04-18

To me, it's extremely difficult(over 500 points)-sorry for that.

Please answer my question as soon as possible. Thank you!!!

I'm a pupil( 14 years old) who have a little experience in using pascal. And it's difficult for me to have to write a program by using pascal.

My problem is "closest pair in the plane problem". Using 2 algorithms: "divide and conquer" and "sweep the plane". Could you give me source code with a complete program.

To me, i will have to try my best to understand algorithms and your code.

Please answer my question as soon as possible. Thank you very much.!!!!

Please answer my question as soon as possible. Thank you!!!

I'm a pupil( 14 years old) who have a little experience in using pascal. And it's difficult for me to have to write a program by using pascal.

My problem is "closest pair in the plane problem". Using 2 algorithms: "divide and conquer" and "sweep the plane". Could you give me source code with a complete program.

To me, i will have to try my best to understand algorithms and your code.

Please answer my question as soon as possible. Thank you very much.!!!!

4 Comments

{ 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^.nex

sortx:= false; head^.next:= sort(head^.next,n);

writeln(closest1.x); { the problem is not important anymore}

readln;

end.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

using a list of objects, Delphi | 3 | 585 | |

TZConnection connected in separate thread | 2 | 985 | |

Delphi XE2 - Company Business System Application, errors when running on Win 7 | 17 | 1,060 | |

FMXGrid getting check box state | 5 | 502 |

how to add IIS SMTP to handle application/Scanner relays into office 365.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**8** Experts available now in Live!