可变的圆 二分？排序？

可变的圆 二分？排序？

问题源自ACM-ICPC 北京赛区2015网络赛题目1 : The Cats' Feeding Spots 大意是这样的，给出m个点，选其中一个点作为圆心画一个圆能把n个点包含在里面（边界不能有点），求最小的半径，找不到这样的半径输出-1。 自己最开始的思路是这样的，以其中一个点作为圆心，然后用伪二分法查找半径（初始化 low=1,high=1416。1000*2^0.5=1414.213），因为毕竟不是高效正统的二分，所以暂时叫它伪二分吧。

#include #include #include #include using namespace std;const int maxn=105;int n,m;struct node{ double x,y;}p[maxn];int r[maxn];double dis(node a,node b){ return fabs(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}int in(int dex,int d){ int res=0; double dd=d*1.0; for(int i=0;i1e-6) res++; } return res;}int mf(int dex){ int low=1,high=1416,mid; //1000*2^0.5=1415 while(low<=high){ mid=(low+high)/2; int sum=in(dex,mid); if(sum>=n) high=mid-1; else return mid; } return mid;}int main(){ //freopen("cin.txt","r",stdin); int t; cin>>t; while(t--){ scanf("%d%d",&m,&n); memset(r,-1,sizeof(r)); for(int i=0;i=1)ans=min(ans,r[i]); } if(ans>1415)puts("-1"); else printf("%d\n",ans); } return 0;}

是的，感觉有点乱，而且时间用了800ms。我看了一份更加优秀的代码，它的思路大致是这样，找圆心的部分也是普通的循环遍历，查找最小半径：对于每一个圆心都计算出它和别的点的距离，然后使用快速排序：

包含n个点的半径应该就是(int)dis[n-1]+1，用ans保存最小的值最后输出结果（不贴代码了，没有别人的许可）。我的做法有许多的修正工作，所以计算次数是100*max(log2(100),100)*100，后者的计算是100*100*(log2(100)，优劣很快就能区分开。总之，提升水平。。。

for(int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。