Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 247
  • Last Modified:

Help me!!!

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.!!!!
0
quacau
Asked:
quacau
  • 3
1 Solution
 
WelkinMazeCommented:
Since this seems like a homework question you have to post some code here that we can look at it and eventually correct your errors if there are some.
0
 
quacauAuthor Commented:
{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.
0
 
quacauAuthor Commented:
This program can't work correctly, if I have a mistake list( head^.next :=list) or i have some mistakes in function merge or function sort, thank you, i'll vote 500 points for you.
0
 
quacauAuthor Commented:
Writeln( closest1.x); ( it can't display, means

 new(head); head^.next:= list;
minresult := maxint;
sortx:= true; head^.next:=sort(head^.next,n);
sortx:= false; head^.next:= sort(head^.next,n);   { implement algorithm}

have some problem, please check it for me.  Thank you...
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now