博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ3564 : [SHOI2014]信号增幅仪
阅读量:6153 次
发布时间:2019-06-21

本文共 808 字,大约阅读时间需要 2 分钟。

先把所有点绕原点逆时针旋转(360-a)度,再把所有点横坐标除以放大倍数p,最后用随机增量法求最小圆覆盖即可。

时间复杂度期望$O(n)$

 

#include
#include
#include
using namespace std;struct P{double x,y;}a[50005],o;inline double dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}inline P center(P x,P y,P z){ double a1=y.x-x.x,b1=y.y-x.y,c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,d=a1*b2-a2*b1; return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};}double r,angle,e,x,y,eps=1e-8;int n,i,j,k;int main(){ srand(199745); for(scanf("%d",&n);i
=r+eps)for(o=a[i],r=0,j=0;j
=r)for(o=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},r=dis(o,a[i]),k=0;k
=r-eps)o=center(a[k],a[j],a[i]),r=dis(o,a[i]); printf("%.3lf",r); return 0;}

  

 

转载地址:http://wjbfa.baihongyu.com/

你可能感兴趣的文章
字符串转日期类型
查看>>
[C++] Test question(1-16)
查看>>
[PHP]require include
查看>>
[C++基础]002_名字空间(namespace)
查看>>
博客开通了。。。
查看>>
零基础也能看懂!写给设计师的前端小知识之排版三步走起来
查看>>
健身减脂报告贴
查看>>
9月--菜鸟吐槽日志
查看>>
关于Django启动创建测试库的问题
查看>>
无法打开物理文件 "X.mdf"。操作系统错误 5:"5(拒绝访问。)"。 (Microsoft SQL Server,错误: 5120)解决...
查看>>
HBase伪分布式安装
查看>>
深入浅出Node.js (附录A) - 安装Node
查看>>
基础知识(2)- Java程序设计环境
查看>>
购物商城Web开发第十八天
查看>>
GridView 的一些信息
查看>>
js 中的闭包
查看>>
Linux学习笔记07—mysql的配置
查看>>
python中硬要写抽象类和抽象方法
查看>>
mybatis 模糊查询 like的三种方式
查看>>
oracle包详解(二)【weber出品】
查看>>