首页 > 其他 > 详细

icpc沈阳网络赛。cake cake!

时间:2018-09-15 13:41:35      阅读:175      评论:0      收藏:0      [点我收藏+]

技术分享图片

题意:给定n个点极其坐标,求画一个至少能包括到m个点的圆,且圆的半径为最小

解题:半径:二分,从给定范围开始即1e4/2;

          一次遍历,以其中任意一点(枚举点)为圆心,画半径为2*r的圆(代表另一个点是否在它的触及范围,此时并不是这个枚举点就是圆心)

在这个大圆范围内的所有点为可触点,以可触点为圆心画半径为r的圆(此步主要是为了极角排序,方便扫描);大圆与这些小圆的交点为端点,其中一个标1,另一个标-1;

然后进行极角排序,为每一个点设立一个极角,方便扫描一圈,然后如果遇到1则表示进入一段含小圆的区域,遇到-1代表离开一段区域,所以+1和-1重复操作,记录过程中最大值。

+1-1的方法也适用于

 

icpc沈阳网络赛。cake cake!

原文:https://www.cnblogs.com/larvie/p/9650653.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!