R的农场

R的农场

题目描述

输入

输出

输入输出样例

chebnear.in

chebnear.out

反思

思路

代码

感觉自己要死了,写了一个晚上,还是木有写出来,我觉得我的思路一点毛病也没有,为什么就是错了!!

先放一份错的,保存一下今天晚上的"成果"!!

OK啦OK啦,我写完啦

我知道为什么我错了!!原来我把题目意思都理解错了!!!!!!!!!我是真心佩服我自己/(ㄒoㄒ)/~~

 #include<bits/stdc++.h>

 #define ll long long

 #define FOR(i,a,b) for(register int i=a;i<=b;i++)

 #define ROF(i,a,b) for(register int i=a;i>=b;i--)

 using namespace std;

 int n,m;

 double K;

 double maxx=;

 int ans;

 int fa[];

 int tmpt[];

 struct ss

 {

     int x,y;

     double p;

 }b[];

 struct ss1

 {

     double X,Y;

     int num;

 }a[],c[];

 int scan()

 {

     int as=,f=;

     char c=getchar();

     while(c>''||c<''){if(c=='-') f=-;c=getchar();}

     while(c>=''&&c<=''){as=(as<<)+(as<<)+c-'';c=getchar();}

     return as*f;

 }

 int ba(int x) {return fa[x]=((fa[x]==x)?x:ba(fa[x]));}

 bool cmp(ss1 i,ss1 j) {return i.X<j.X;}

 bool cmp2(ss1 i,ss1 j) {return i.Y<j.Y;}

 bool cmp3(ss i,ss j)   {return i.p<j.p;}

 bool  clst(int l,int r)

 {

     int mid=(l+r)>>;

     if(l>=r) return ;

     if(!clst(l,mid)||!clst(mid+,r)) return ;

     int k=;

     while(a[l].X+K<a[mid].X) l++;

     while(a[r].X-K>a[mid].X) r--;

     FOR(i,l,r) c[++k]=a[i];

     sort(c+,c+k+,cmp2);

     FOR(i,,k)

     {

         FOR(j,i+,k)

         {

             if(c[j].Y-c[i].Y>K) break;

             if(ba(c[i].num)!=ba(c[j].num))

             {

                 if(abs(c[i].X-c[j].X)<=K)

                     return ;

             }

         }

     }

     return ;

 }

 bool chek(int mid)

 {

     FOR(i,,n) fa[i]=i;//父亲的赋值

     FOR(i,,m)

     {

         if(b[i].p>b[mid].p) break;

         int f1=ba(b[i].x),f2=ba(b[i].y);//父亲的赋值

         if(f1!=f2)

             fa[f1]=f2;

     }

     return clst(,n);

 }

 int main()

 {

     n=scan();m=scan();

     scanf("%lf",&K);

     FOR(i,,n) scanf("%lf%lf",&a[i].X,&a[i].Y),a[i].num=i;

     sort(a+,a+n+,cmp);//按照X的关键字排序

     FOR(i,,m)

     {

         b[i].x=scan();b[i].y=scan();scanf("%lf",&b[i].p);

     }

     sort(b+,b+m+,cmp3);//按照和解费排序

     int l=,r=m-;

     while(l<=r)

     {

         int mid=(l+r)>>;

         //cout<<mid<<endl;

         if(chek(mid))

         {

             //        cout<<"NBV"<<" "<<mid<<endl;

             r=mid-;

         }

         else l=mid+;

     }//zh这个二分其实不是很懂...

 //    cout<<ans-1<<endl;

     printf("%.3lf",b[l].p);

 }

 //找了半天发现是排序的错,我也是佛系了.......