2012-A3-0014

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：有N组，每组有2个球心坐标，要从每组中选一个球心，使得选取的球之间两两不相交的半径最大。

i和i+n是二选一的一组，先计算所有不是同一组的球两两之间的距离，然后从小到大排序。

在上面计算的距离中二分距离，然后距离小于等于二分值的每个点对（a,b）（A和a同组，B和b同组）

建立有向边a->B, b->A,因为a，b不能同时在，那么选了a就要选B，选了b就要选A...

最后如果边确定了，某个点i+n->i ,且i->i+n,那么这种方案是不可行的，所以答案值比它小，

即 i+n 和 i 在同一个强连通分量里面.

注意题目中的舍入方式是向下取整.

{{{
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef size_t u32;
typedef pair<u32,u32> dij;
dij ee[80000];
int x[400],y[400],z[400];
u32 n;
u32 sqr(int x)  {return x*x;}
u32 dist(u32 i,u32 j){return sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);}
u32 neg(u32 x)  {return (x<n)?x+n:x-n;}
namespace Gabow{
    const u32 MAXN = 400;
    u32 e[80000],nx[80000],p[MAXN],pre[MAXN],
        id[MAXN],s[MAXN+1],r[MAXN+1],m,n,S,R,c,t;
#define clr(x) memset(x,0xff,n<<2)
    void init(u32 _){n=_;m=S=R=c=t=0;clr(p);clr(id);clr(pre);}
    void ae(u32 a,u32 b){e[m]=b;nx[m]=p[a];p[a]=m++;}
    void dfs(u32 u){
        pre[s[++S]=r[++R]=u]=t++;
        for(u32 i=p[u],v;~i;i=nx[i])
        if(~pre[v=e[i]]){
            if(!~id[v])while(pre[r[R]]>pre[v])--R;
        }else dfs(v);
        if(r[R]==u){--R;do id[s[S]]=c;while(s[S--]!=u);c++;}
    }
    u32 scc(){for(u32 i=0;i<n;++i)if(!~pre[i])dfs(i);return c;}
}
int main(){
    for(u32 m,ans;~scanf("%u",&n);){
        for(u32 i=m=0;i<n;++i){
            scanf("%d%d%d%d%d%d",x+i,y+i,z+i,x+i+n,y+i+n,z+i+n);
            for(u32 j=0;j<i;++j){
                ee[m++]=dij(dist(i,j),i<<16|j);
                ee[m++]=dij(dist(i+n,j),i+n<<16|j);
                ee[m++]=dij(dist(i,j+n),i<<16|j+n);
                ee[m++]=dij(dist(i+n,j+n),i+n<<16|j+n);
            }
        }
        sort(ee,ee+m);
        u32 l=1,r=m-1;
        for(u32 x;l+1<r;){
            Gabow::init(n<<1);
            for(x= l+r>>1;x<r&&ee[x+1].first==ee[x].first;++x);
            for(u32 i=0,a,b;i<=x;++i){
                Gabow::ae(a=ee[i].second>>16,neg(b=ee[i].second&511));
                Gabow::ae(b,neg(a));
            }
            Gabow::scc();
            for(u32 i=0;i<=n;++i)
            if(i<n){if(Gabow::id[i]==Gabow::id[i+n]){for(r=x;r>l&&ee[r].first==ee[r-1].first;--r);break;}}
            else l=x;
        }
        l =sqrt(ee[r].first*250000.0);
        printf("%u.%u\n",l/1000,l%1000);
    }
    return 0;
}
}}}

{{{
因为并查集是不对的，边是有向边，反过来不一定成立
我一开始写也想偷懒写成并查集后来发现有问题
By 猛犸也钻地
}}}

题意：有N组，每组有2个球心坐标，要从每组中选一个球心，使得选取的球之间两两不相交的半径最大。

一下做法只能过样例，不能AC，不知是算法错误还是实现错误，求编辑......

我的做法是：i和i+n是二选一的一组，先计算所有不是同一组的球两两之间的距离，然后从小到大排序，

然后从小到大枚举上面求出距离(设这是球A(与他同一组的是A')和球B的距离)，如果认为半径的两倍小于此距离，那么这两个球A,B必然不能同时选择，

于是A只能和B'同时选择,B只能和A'可以同时选择,用并查集维护这种关系。

如果枚举到某条距离后，存在某个球心C和他同组的C'在同一个集合时，说明此半径的2倍大于此距离会使选取关系无法满足，此距离除2就是答案？

{{{
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef size_t u32;
typedef pair<u32,u32> dij;
dij ee[80000];
int x[400],y[400],z[400];
u32 f[400],n;
inline u32 sqr(int x)   {return x*x;}
inline u32 dist(u32 i,u32 j){return sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);}
inline u32 neg(u32 x)   {return (x<n)?x+n:x-n;}
u32 ff(u32 x)           {return x!=f[x]?f[x]=ff(f[x]):x;}
void merge(u32 i,u32 j) {f[ff(j)]=ff(i);}
int main(){
    for(u32 m,ans;~scanf("%u",&n);){
        for(u32 i=m=0;i<n;++i){
            scanf("%d%d%d%d%d%d",x+i,y+i,z+i,x+i+n,y+i+n,z+i+n);
            for(u32 j=0;j<i;++j){
                ee[m++]=dij(dist(i,j),i<<16|j);
                ee[m++]=dij(dist(i+n,j),i+n<<16|j);
                ee[m++]=dij(dist(i,j+n),i<<16|j+n);
                ee[m++]=dij(dist(i+n,j+n),i+n<<16|j+n);
            }
        }
        sort(ee,ee+m);ee[m].first=~0;
        for(u32 i=0;i<n<<1;++i)f[i]=i;
        for(u32 i=0;i<m;){
            ans=ee[i].first;
            for(u32 a,b;ee[i].first==ans;++i){
                a=ee[i].second>>16;b=ee[i].second&511;
                merge(neg(a),b);
                merge(neg(b),a);
            }
            for(u32 j=0;j<n;++j)
                if(ff(j)==ff(j+n))
                    i=m;
        }
        printf("%.3lf\n",sqrt(ans*0.25));
    }
    return 0;
}
}}}

题意：有N组，每组有2个球心坐标，要从每组中选一个球心，使得选取的球之间两两不相交的半径最大。

i和i+n是二选一的一组，先计算所有不是同一组的球两两之间的距离，然后从小到大排序。

在上面计算的距离中二分距离，然后距离小于等于二分值的每个点对（a,b）（A和a同组，B和b同组）

建立有向边a->B, b->A,因为a，b不能同时在，那么选了a就要选B，选了b就要选A...

最后如果边确定了，某个点i+n->i ,且i->i+n,那么这种方案是不可行的，所以答案值比它小，

即 i+n 和 i 在同一个强连通分量里面.

注意题目中的舍入方式是向下取整.

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef size_t u32;
typedef pair<u32,u32> dij;
dij ee[80000];
int x[400],y[400],z[400];
u32 n;
u32 sqr(int x)  {return x*x;}
u32 dist(u32 i,u32 j){return sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);}
u32 neg(u32 x)  {return (x<n)?x+n:x-n;}
namespace Gabow{
    const u32 MAXN = 400;
    u32 e[80000],nx[80000],p[MAXN],pre[MAXN],
        id[MAXN],s[MAXN+1],r[MAXN+1],m,n,S,R,c,t;
#define clr(x) memset(x,0xff,n<<2)
    void init(u32 _){n=_;m=S=R=c=t=0;clr(p);clr(id);clr(pre);}
    void ae(u32 a,u32 b){e[m]=b;nx[m]=p[a];p[a]=m++;}
    void dfs(u32 u){
        pre[s[++S]=r[++R]=u]=t++;
        for(u32 i=p[u],v;~i;i=nx[i])
        if(~pre[v=e[i]]){
            if(!~id[v])while(pre[r[R]]>pre[v])--R;
        }else dfs(v);
        if(r[R]==u){--R;do id[s[S]]=c;while(s[S--]!=u);c++;}
    }
    u32 scc(){for(u32 i=0;i<n;++i)if(!~pre[i])dfs(i);return c;}
}
int main(){
    for(u32 m,ans;~scanf("%u",&n);){
        for(u32 i=m=0;i<n;++i){
            scanf("%d%d%d%d%d%d",x+i,y+i,z+i,x+i+n,y+i+n,z+i+n);
            for(u32 j=0;j<i;++j){
                ee[m++]=dij(dist(i,j),i<<16|j);
                ee[m++]=dij(dist(i+n,j),i+n<<16|j);
                ee[m++]=dij(dist(i,j+n),i<<16|j+n);
                ee[m++]=dij(dist(i+n,j+n),i+n<<16|j+n);
            }
        }
        sort(ee,ee+m);
        u32 l=1,r=m-1;
        for(u32 x;l+1<r;){
            Gabow::init(n<<1);
            for(x= l+r>>1;x<r&&ee[x+1].first==ee[x].first;++x);
            for(u32 i=0,a,b;i<=x;++i){
                Gabow::ae(a=ee[i].second>>16,neg(b=ee[i].second&511));
                Gabow::ae(b,neg(a));
            }
            Gabow::scc();
            for(u32 i=0;i<=n;++i)
            if(i<n){if(Gabow::id[i]==Gabow::id[i+n]){for(r=x;r>l&&ee[r].first==ee[r-1].first;--r);break;}}
            else l=x;
        }
        l =sqrt(ee[r].first*250000.0);
        printf("%u.%u\n",l/1000,l%1000);
    }
    return 0;
}

因为并查集是不对的，边是有向边，反过来不一定成立
我一开始写也想偷懒写成并查集后来发现有问题
By 猛犸也钻地

题意：有N组，每组有2个球心坐标，要从每组中选一个球心，使得选取的球之间两两不相交的半径最大。

一下做法只能过样例，不能AC，不知是算法错误还是实现错误，求编辑......

我的做法是：i和i+n是二选一的一组，先计算所有不是同一组的球两两之间的距离，然后从小到大排序，

然后从小到大枚举上面求出距离(设这是球A(与他同一组的是A')和球B的距离)，如果认为半径的两倍小于此距离，那么这两个球A,B必然不能同时选择，

于是A只能和B'同时选择,B只能和A'可以同时选择,用并查集维护这种关系。

如果枚举到某条距离后，存在某个球心C和他同组的C'在同一个集合时，说明此半径的2倍大于此距离会使选取关系无法满足，此距离除2就是答案？

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef size_t u32;
typedef pair<u32,u32> dij;
dij ee[80000];
int x[400],y[400],z[400];
u32 f[400],n;
inline u32 sqr(int x)   {return x*x;}
inline u32 dist(u32 i,u32 j){return sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);}
inline u32 neg(u32 x)   {return (x<n)?x+n:x-n;}
u32 ff(u32 x)           {return x!=f[x]?f[x]=ff(f[x]):x;}
void merge(u32 i,u32 j) {f[ff(j)]=ff(i);}
int main(){
    for(u32 m,ans;~scanf("%u",&n);){
        for(u32 i=m=0;i<n;++i){
            scanf("%d%d%d%d%d%d",x+i,y+i,z+i,x+i+n,y+i+n,z+i+n);
            for(u32 j=0;j<i;++j){
                ee[m++]=dij(dist(i,j),i<<16|j);
                ee[m++]=dij(dist(i+n,j),i+n<<16|j);
                ee[m++]=dij(dist(i,j+n),i<<16|j+n);
                ee[m++]=dij(dist(i+n,j+n),i+n<<16|j+n);
            }
        }
        sort(ee,ee+m);ee[m].first=~0;
        for(u32 i=0;i<n<<1;++i)f[i]=i;
        for(u32 i=0;i<m;){
            ans=ee[i].first;
            for(u32 a,b;ee[i].first==ans;++i){
                a=ee[i].second>>16;b=ee[i].second&511;
                merge(neg(a),b);
                merge(neg(b),a);
            }
            for(u32 j=0;j<n;++j)
                if(ff(j)==ff(j+n))
                    i=m;
        }
        printf("%.3lf\n",sqrt(ans*0.25));
    }
    return 0;
}