题意

在两个点集中，找出距离最近的两个点，求出这个距离

分析

又是学习之后才会做，最小点对。

思想是二分，将点以x坐标排序，然后分为两部分，在这两部分中分别求出最近的距离，然后可以得到一个ans=min(ansl,ansr)。

但是还需要处理中间部分，可知能比ans这个距离还小的，横坐标一定是在(mid-ans,mid+ans)之间，否则光横坐标就已经GG了

还有一个纵坐标的问题。将刚刚筛选出来可能使答案更小的点以y坐标排序，同理，当y坐标的跨度>ans后就GG了

看起来枚举这些x,y时间复杂度很大，然而这个枚举是6次，根据抽屉原理可以证明，我研究了挺久也不会，直面自己的弱......

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using  namespace std;#define N 300100#define oo 1e15  struct email{    double x,y;    int c;}a[N],tmp[N];double ans; int t,n,mid,cnt;bool cmpx(email a,email b){    return a.x
          
           >1,cnt=0; ans=min(check(l,mid),check(mid+1,r)); for(int i=l;i<=r;i++) if(fabs(a[i].x-a[mid].x)
           
            ans)break; ans=min(ans,d(tmp[i],tmp[j])); } return ans; }int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y),a[i].c=0; for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i+n].x,&a[i+n].y),a[i+n].c=1; sort(a+1,a+n*2+1,cmpx); printf("%.3lf\n",check(1,2*n)); } return 0;}

转载于:https://www.cnblogs.com/NSD-email0820/p/9630437.html

转载地址：https://blog.csdn.net/weixin_30719711/article/details/98314699 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【学习总结】win7使用anaconda安装tensorflow+keras

下一篇：sdut oj 2216 CIVIC DILL MIX

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意

分析

发表评论

最新留言

关于作者

推荐文章