首页 > 代码库 > [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.
其实说起来也不是很难,增量法我在考场居然也想到了,就是那时没想到可以以原点为中心,算法也写的有问题- -
来一发考场逗比错误代码,有空分析下错哪里了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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。