首页 > 代码库 > [SHTSC 2014] 信号增幅仪

[SHTSC 2014] 信号增幅仪

最小覆盖圆算法。看着题解半蒙半抄的搞过去了…

主要参考以下
http://blog.csdn.net/acdreamers/article/details/9406735
http://blog.csdn.net/lthyxy/article/details/6661250
http://blog.himdd.com/archives/2666

其中有一个求外心的过程是错的…害我调了好久…还把x和y搞反…可是就算是错的我居然过了80%的数据…

仍然几个疑问:

(1)最小覆盖圆算法时间复杂度的证明

(2)椭圆的中心未定的情况下,为什么以原点为中心旋转&缩放即可?(我几何不好QAQ)

program amplifier;uses math;type point=record             x,y:extended;           end;const maxn=50000;      pi=3.14159265358979;      eps=0.00000001;var n,i,p:longint;    a,r:extended;    o:point;    v:array[1..maxn+10] of point;procedure rotate(i:longint);var x,y:extended;begin  x:=v[i].x*cos(-a)-v[i].y*sin(-a);  y:=v[i].x*sin(-a)+v[i].y*cos(-a);  v[i].x:=x/p;  v[i].y:=y;end;function circumcenter(p,q,r:point):point;var a,b,c,d,e,f:extended;begin  a:=q.x-p.x;  b:=q.y-p.y;  c:=-(q.x*q.x+q.y*q.y-p.x*p.x-p.y*p.y)/2;  d:=r.x-p.x;  e:=r.y-p.y;  f:=-(r.x*r.x+r.y*r.y-p.x*p.x-p.y*p.y)/2;  circumcenter.y:=(-c*d+f*a)/(b*d-e*a);  circumcenter.x:=(-c*e+f*b)/(a*e-b*d);end;function dis(a,b:point):extended;begin  dis:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));end;procedure min_cover_circle;var i,j,k:longint;begin  o:=v[1];r:=0;  for i:=2 to n do    begin      if dis(v[i],o)>r+eps then        begin          o:=v[i];r:=0;          for j:=1 to i do            if dis(v[j],o)>r+eps then              begin                o.x:=(v[i].x+v[j].x)/2;                o.y:=(v[i].y+v[j].y)/2;                r:=dis(v[j],o);                for k:=1 to j do                  if dis(v[k],o)>r+eps then                    begin                      o:=circumcenter(v[i],v[j],v[k]);                      r:=dis(o,v[i]);                    end;              end;        end;    end;end;begin  //assign(input,amplifier20.in);reset(input);  //assign(output,amplifier20.out);rewrite(output);  readln(n);  for i:=1 to n do    readln(v[i].x,v[i].y);  readln(a);a:=a/180*pi;  readln(p);  for i:=1 to n do    rotate(i);  if n=2 then    begin      writeln(dis(v[1],v[2])/2:0:3);      //close(input);close(output);      halt;    end;  min_cover_circle;  writeln(r:0:3);  //close(input);close(output);end.
amplifier

其实说起来也不是很难,增量法我在考场居然也想到了,就是那时没想到可以以原点为中心,算法也写的有问题- -
来一发考场逗比错误代码,有空分析下错哪里了0 0

program amplifier;uses math;const pi=3.141592653589;type vtype=record             x,y:real;           end;var n,p,i,n1,n2,n3:longint;    xx,yy,xt,yt,a,aa,x0,y0:real;    v:array[0..50010] of vtype;procedure cac(x1,y1,x2,y2,x3,y3:real);var a1,a2,b1,b2,c1,c2:real;begin  if x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3=0 then exit;  a1:=2*(x1-x3);b1:=2*p*p*(y1-y3);c1:=(x1*x1-x3*x3)+p*p*(y1*y1-y3*y3);  a2:=2*(x1-x2);b2:=2*p*p*(y1-y2);c2:=(x1*x1-x2*x2)+p*p*(y1*y1-y2*y2);  xt:=(b2*c1-b1*c2)/(a1*b2-a2*b1);  yt:=(a1*c2-a2*c1)/(a1*b2-a2*b1);  a:=sqrt(sqr(x1-xt)+p*p*sqr(y1-yt));end;function ini(t:integer;x0,y0,a:real):boolean;var tt:real;begin  tt:=sqr(v[t].x-x0)+p*p*sqr(v[t].y-y0);  if tt<=a*a then exit(true) else exit(false);end;procedure work2;begin  xx:=(v[n1].x+v[n2].x)/2;  yy:=(v[n1].y+v[n2].y)/2;  a:=sqrt(sqr(v[n1].x-xx)+p*p*sqr(v[n1].y-yy));  writeln((a/p):0:3);end;function line(n1,n2,n3:integer):boolean;var x1,x2,x3,y1,y2,y3:real;begin  x1:=v[n1].x;x2:=v[n2].x;x3:=v[n3].x;  y1:=v[n1].y;y2:=v[n2].y;y3:=v[n3].y;  if x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3=0 then exit(true) else exit(False);end;procedure workline;begin  if ((v[n1].x<v[n2].x) and (v[n2].x<v[n3].x)) or ((v[n3].x<v[n2].x) and (v[n2].x<v[n1].x)) then    begin      n2:=n3;n3:=n3+1;exit;    end;  if ((v[n2].x<v[n1].x) and (v[n1].x<v[n3].x)) or ((v[n3].x<v[n1].x) and (v[n1].x<v[n2].x)) then    begin      n1:=n2;n2:=n3;n3:=n3+1;exit;    end;  if ((v[n1].x<v[n3].x) and (v[n3].x<v[n2].x)) or ((v[n2].x<v[n3].x) and (v[n3].x<v[n1].x)) then    begin      n3:=n3+1; exit;    end;end;begin  assign(input,amplifier.in);reset(input);  assign(output,amplifier.out);rewrite(output);  readln(n);  for i:=1 to n do    readln(v[i].x,v[i].y);  readln(a);readln(p);  for i:=1 to n do    begin      x0:=v[i].x;y0:=v[i].y;      v[i].x:=cos(-a/180*pi)*x0-sin(-a/180*pi)*y0;      v[i].y:=sin(-a/180*pi)*x0+cos(-a/180*pi)*y0;    end;  v[n+1].x:=200000000;v[n+1].y:=200000001;  if n=1 then writeln(0);  if n=2 then    begin      n1:=1;n2:=2;      work2;    end;  if n>=3 then    begin      n1:=1;n2:=2;n3:=3;      while (line(n1,n2,n3)) and (n3<>n+1) do workline;      if n3=n+1 then        begin          work2;          exit;        end;      cac(v[n1].x,v[n1].y,v[n2].x,v[n2].y,v[n3].x,v[n3].y);      xx:=xt;yy:=yt;aa:=a;      for i:=n3+1 to n do        begin          if not ini(i,xx,yy,aa) then            begin              cac(v[n1].x,v[n1].y,v[n2].x,v[n2].y,v[i].x,v[i].y);              if ini(n3,xt,yt,a) then                begin                  n3:=i;xx:=xt;yy:=yt;aa:=a;continue;                end;              cac(v[n1].x,v[n1].y,v[i].x,v[i].y,v[n3].x,v[n3].y);              if ini(n2,xt,yt,a) then                begin                  n2:=n3;n3:=i;xx:=xt;yy:=yt;aa:=a;continue;                end;              cac(v[i].x,v[i].y,v[n2].x,v[n2].y,v[n3].x,v[n3].y);              if ini(n1,xt,yt,a) then                begin                  n1:=n2;n2:=n3;n3:=i;xx:=xt;yy:=yt;aa:=a;continue;                end;            end;        end;      writeln((a/p):0:3);    end;  close(input);close(output);end.
amplifier-wrong