Antenna – CEOI 2006

 

Download test and check program

-         Compile your code

-         Run antenna.bat

 

This program uses the algorithm from CEOI’s offical solution, but it ran slowly !

 

antenna.pas

 

program antenna;

 

const M=500;

      E=1E-6;

 

{---------------------------------------------------}

 

function atan2(x, y: real): real; {return the angle between P(x, y) and x-axis}

var r: real;

begin

        if (x=0) then

        begin

                if (y>=0) then

                        r:=pi/2

                else

                        r:=-pi/2;

        end else

        begin

             r:=arctan(abs(y/x));

             if (y>=0) and (x<=0) then

                     r:=pi-r

             else if (y<=0) and (x<=0) then

                     r:=r+pi

             else if (y<=0) and (x>=0) then

                     r:=2*pi-r;

        end;

        atan2:=r;

end;

 

function arccos(x: real): real;

begin

   arccos:=arctan(sqrt(1-sqr(x))/x)

end;

 

type tp=record x, y: real; end;

 

function d(a, b: tp): real;

begin

     d:=sqrt(sqr(b.x-a.x)+sqr(b.y-a.y));

end;

 

{---------------------------------------------------}

 

var n, k: integer;

    a: array[1..M] of tp;

 

{---------------------------------------------------}

 

const eenter=0; eexit=1;

 

type te=

    record

          a: real;

          e: integer;

    end;

 

var ev: array[1..4*M] of te;

    ne: integer;

 

procedure addevent(a: real; e: integer);

begin

     inc(ne);

     ev[ne].a:=a;

     ev[ne].e:=e;

end;

 

procedure qsorte(l, r: integer);

var i, j: integer; p: real; t: te;

begin

     if l > r then exit;

     i:=l; j:=r; p:=ev[(i+j) div 2].a;

     repeat

           while ev[i].a < p do inc(i);

           while p < ev[j].a do dec(j);

           if i<=j then

           begin

                t:=ev[i]; ev[i]:=ev[j]; ev[j]:=t;

                inc(i); dec(j);

           end;

     until i > j;

     if l<j then qsorte(l, j);

     if i < r then qsorte(i, r);

end;

 

procedure sortevents;

begin

     qsorte(1, ne);

end;

 

{---------------------------------------------------}

 

var c: tp; {center}

 

function foundcircle2(r: real; x: integer): boolean;

var i, cnt: integer;

    p, q: tp;

    alpha, beta, a1, a2:real;

begin

     foundcircle2:=true;

 

     p:=a[x]; ne:=0;

     for i:=1 to n do

         if (i<>x) and (d(p, a[i])<=2*r) then

         begin

              q:=a[i];

              alpha:=atan2(q.x-p.x, q.y-p.y);

              beta:=arccos(d(p, q) / (2*r));

              {alpha = xPQ, |beta|=QPO, thus the angle between OP

              and x-axis is xPO=xPQ+QPO=alpha +/- beta}

 

              a1:=alpha-beta;

              a2:=alpha+beta;

 

              addevent(a1, eenter);

              addevent(a2, eexit);

              addevent(a1+2*pi, eenter); {set cnt=1 initially and use two rotations}

              addevent(a2+2*pi, eexit)

         end;

 

     sortevents;

 

     {-------------------------}

 

     cnt:=1;

     for i:=1 to ne do

     if ev[i].e = eenter then

     begin

        inc(cnt);

        if cnt = k then

        begin

             c.x:=p.x+r*cos(ev[i].a);

             c.y:=p.y+r*sin(ev[i].a);

             exit;

        end;

     end

     else

         dec(cnt);

 

     foundcircle2:=false;

end;

 

function foundcircle(r: real): boolean;

var i: integer;

begin

        foundcircle:=true;

        for i:=1 to n do

                if foundcircle2(r, i) then

                   exit;

        foundcircle:=false;

end;

 

{---------------------------------------------------}

 

var radius: real;

 

procedure _input;

var i: integer;

begin

        readln(n, k);

        for i:=1 to n do

                readln(a[i].x, a[i].y);

end;

 

 

procedure _solve;

var i, j, r: real;

begin

        i:=0;        j:=20000;

        repeat

                r:=(i+j)/2;

                if foundcircle(r) then

                begin

                        radius:=r;

                        j:=r

                end

                else

                        i:=r;

        until (j-i<E);

end;

 

procedure _output;

begin

     writeln(radius:0:6);

     writeln(c.x:0:6, ' ',c.y:0:6);

end;

 

begin

        _input;

        _solve;

        _output;

end.