当前位置: 首页 > news >正文

苏州智能网站开发电商商城网站建设方案

苏州智能网站开发,电商商城网站建设方案,竹子网站建站,自己有网站 做app吗文章目录题目描述数据范围解析代码图片转载自#xff1a; https://blog.csdn.net/weixin_43346722/article/details/118435430题目描述 平面上有 n个点#xff0c;用n个大小相同的圆分别将一个点作为圆心#xff0c;同时满足圆圈不相交#xff0c;求圆的最大半径。 数据范… 文章目录题目描述数据范围解析代码图片转载自 https://blog.csdn.net/weixin_43346722/article/details/118435430题目描述 平面上有 n个点用n个大小相同的圆分别将一个点作为圆心同时满足圆圈不相交求圆的最大半径。 数据范围 2n2e52n2e52n2e5 解析 把题目抽象一下就是求最小的一对点的距离除以2 考虑如何求呢 暴力当然是会T飞的 首先把所有点按x排序 然后考虑分治 分治的关键是如何把两个小问题合并 暴力合并还是n方… 我们考虑剪掉一些不必要的比较 设两边分别得到的答案的最小值为a 那么x距离大于a的肯定不用比了 但是一旦x的距离全在a里面咋办 同理我们按y再排一下序y的距离大于a都不用算了 那么每个点对应的的计算范围大概就是这样 那么这样就不会有很多点了吗 我们还有一个了一个关键性质左边和右边的点各自之间的距离都不小于a 那么右边这个矩形里能填的两两距离不小于a的点就不多了 关于这个我们就要使用神奇的鸽巢原理 考虑矩形按照下面这个图分区 每个小矩形的对角线长度小于a所以每个矩形最多有一个点 所以大矩形内的点不超过6个 同时我们把6个点放到四角和两长边的终点其实也就可以构造出6个的方案 所以我们每个点需要计算的点最多不超过6个 时间复杂度降为线性问题得以解决 整体复杂度nlognnlognnlogn每次合并按ysort可能再大一些 代码 #includebits/stdc.h using namespace std; const int N2e5100; const int M2e6100; #define ll long long ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f; } int n,m; struct node{double x,y; }p[N],tmp[N],now[N]; bool cmpx(node a,node b){return a.xb.x;} bool cmpy(node a,node b){return a.yb.y;} double dis(node a,node b){//printf( dis:);print(a);print(b);printf(%lf%lf%lf)return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y)); } void print(node o){printf((%.2lf %.2lf),o.x,o.y);} double solve(int l,int r){if(lr) return 2e9;int mid(lr)1;double resmin(solve(l,mid),solve(mid1,r));int num0,tot0;for(int imid1;ir;i){if(p[i].x-p[mid].xres) break;tmp[num]p[i];//printf(tmp:);print(p[i]);putchar(\n);}for(int imid;il;i--){if(p[mid1].x-p[i].xres) break;now[tot]p[i];//printf(now:);print(p[i]);putchar(\n);}sort(tmp1,tmp1num,cmpy);sort(now1,now1tot,cmpy);int pre1;for(int i1;itotprenum;i){while(prenumnow[i].y-tmp[pre].yres) pre;for(int jpre;tmp[j].y-now[i].yresjnum;j){//printf(i%d j%d dis%.2lf,i,j,dis(now[i],tmp[j]));print(now[i]);print(tmp[j]);putchar(\n);resmin(res,dis(now[i],tmp[j]));}}return res; } int main(){while(1){nread();if(n0) return 0;for(int i1;in;i){scanf(%lf%lf,p[i].x,p[i].y);}sort(p1,p1n,cmpx);printf(%.2lf\n,solve(1,n)/2);}return 0; } /* 2 0 0 1 1 2 1 1 1 1 3 -1.5 0 0 0 0 1.5 0 */
http://www.sadfv.cn/news/259067/

相关文章:

  • 广告网站定制如何建设淘宝网站首页
  • 太原经济型网站建设价格鄂州做网站多少钱
  • 昆山网站开发的公司深圳服务平台网站
  • 基础网站开发网站所属网络
  • 广州做外贸网站公司wordpress好处
  • 北京大兴网站建设首选公司做前端网站用什么工具
  • 新建免费网站免费注册网站
  • 非经营备案网站能贴放广告么网站开发证有没有用
  • 关于公司网站建设请示网络推广计划书范文
  • 素材网站php程序源码深圳外贸推广公司
  • 做磁性材料在哪些网站推广比较好wordpress 置顶 函数
  • 网站外链建设可以提升网站网站建设投入产出分析
  • 如何做企业网站加v注册公司需要什么条件和材料
  • 廊坊网络公司网站php 开发手机网站
  • 沧州市网站建设智慧团建电脑版入口
  • 山东省建设局拖欠工资网站陈木胜妻子
  • ac域名网站wordpress 页面内菜单
  • 如何在百度网站收录提交入口免费的网络营销方式有哪些
  • 做网站工作职责软件培训机构有哪些?哪个比较好
  • 商丘企业网站建设团队seo网络推广经理招聘
  • 免费网站应用怎么在百度上面做网站
  • 网站查询ip地址wordpress什么意思
  • 南阳网站开发公司晚上必看的正能量直播app
  • 曲阳县做网站怎么推广业务
  • 中国交建招标平台南宁seo品牌费用是多少
  • 如何使用c 进行网站开发心跳直播视频免费下载
  • 某品牌休闲零食网站建设规划书做网站的基本功
  • 天安云谷网站建设wordpress短消息
  • 站长工具高清吗网络营销的基本职能有哪些
  • 只买域名不建网站聊城做网站的公司渠道