Help me!!!

Posted on 2006-04-18
Last Modified: 2010-04-16
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.!!!!
Question by:quacau
    LVL 11

    Accepted Solution

    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.

    Author Comment

    {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;

    point = record
    x: real;
    y: real;
    link = ^node;
    node = record
    p: point;
    next: link;

    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;
    list12:= keeptrack ;   {it seems to be unlimited loop, really difficult or i have a wrong list that declares in the main program }
    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;

    procedure check(p1,p2: point);         { it's easy, i got it}
    var distance : real;
    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;

    function sort(c: link; n: integer):link;
    var a,b: link;
        i: integer;
        middle: real;
        p1,p2,p3,p4: point;
    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
    a:= c; p1:=keeptrack^.p; p2:=keeptrack^.p; p3:= keeptrack^.p; p4:= keeptrack^.p;
    if abs(a^.p.x - middle) < minresult then
       begin check(a^.p,p1);
             p1:=p2; p2:=p3; p3:=p4; p4:=a^.p;
    a:= a^.next;
    until a=keeptrack ;

    begin          { please check this for me,do i have s mistakes}
    keeptrack^.p.x:= maxint;
    keeptrack^.p.y:= maxint;
    writeln('how many points are there on the plane: ????');
    list := nil;
    for v:=1 to n do begin
    first^.p.x := random(1000);
    first^.p.y := random(1000);
    first^.next := list;
    list := first;

    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}


    Author Comment

    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.

    Author Comment

    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...

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How to run any project with ease

    Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
    - Combine task lists, docs, spreadsheets, and chat in one
    - View and edit from mobile/offline
    - Cut down on emails

    Create and license users in Office 365 in bulk based on a CSV file. A step-by-step guide with PowerShell script examples.
    ADCs have gained traction within the last decade, largely due to increased demand for legacy load balancing appliances to handle more advanced application delivery requirements and improve application performance.
    how to add IIS SMTP to handle application/Scanner relays into office 365.
    Access reports are powerful and flexible. Learn how to create a query and then a grouped report using the wizard. Modify the report design after the wizard is done to make it look better. There will be another video to explain how to put the final p…

    760 members asked questions and received personalized solutions in the past 7 days.

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

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    8 Experts available now in Live!

    Get 1:1 Help Now