prow2012-A3-0014

从 Trac 迁移的文章

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

原文章内容如下：

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

较裸的2-sat判定问题，二分了某个半径R后，可以根据是否会冲突决定建图，比如a组的0会碰到b组的1，那么建边就是a_0-->b_0

在建出的图上求强联通分量，如果a_0,a_1在同一强联通分量内，即false.


{{{

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;

struct edges {
    int node, next;
} edge[400000], edge2[400000];
int node[1000], node2[1000], num, num2, belong[1000],Q[10000];
int N;
double D[500][2][3];
void add(int a, int b, edges *tmpedge, int *tmpnode, int &num) {
    tmpedge[num].node = b;
    tmpedge[num].next = tmpnode[a];
    tmpnode[a] = num++;
}
bool mark[1000];
int T[10000];
int Knum, Tnum;

void dfs1(int now) {  //?????DFS
    mark[now] = true;
    for (int i = node[now]; i != -1; i = edge[i].next)
        if (!mark[edge[i].node]) dfs1(edge[i].node);
    T[Tnum++] = now;
}

void dfs2(int now) {   //????????DFS
    belong[now] = Knum;
    mark[now] = true;
    for (int i = node2[now]; i != -1; i = edge2[i].next)
        if (!mark[edge2[i].node]) dfs2(edge2[i].node);
    return;
}
double sqr(double x){
    return x*x;
}
double eps = 1e-6;
double calcD(int i,int k1,int j,int k2){
    double ans = 0;
    for (int t=0;t<3;t++)
        ans+=sqr(D[i][k1][t]-D[j][k2][t]);
    return sqrt(ans);
}
bool check(double mid){
    int i,j,k1,k2;
        num = num2 = 0;
        memset(node, -1, sizeof (node));
        memset(node2, -1, sizeof (node2));
        for (i=0;i<N;i++)
            for (j=0;j<N;j++)
                if (i!=j){
                    for (k1 = 0;k1<2;k1++)
                        for (k2=0;k2<2;k2++){
                            if (calcD(i,k1,j,k2)<mid*2){
                                add(i*2+k1, j*2+1-k2, edge, node, num);
                                add(j*2+1-k2, i*2+k1, edge2, node2, num2);
                            }
                        }
                }
        Tnum = Knum = 0;
        memset(mark, false, sizeof (mark));
        for (i = 0; i < 2 * N; i++)
            if (!mark[i])
                dfs1(i);
        memset(mark, false, sizeof (mark));
        for (i = Tnum - 1; i >= 0; i--) {  //???????DFS
            if (!mark[T[i]])
            {
                Q[Knum] = T[i];        //????????????????
                dfs2(T[i]), Knum++;
            }
        }
        for (i=0;i<2*N;i+=2)
            if (belong[i]==belong[i+1])
            {
                return false;

            }
        return true;
}



int main() {

    int a, b, i, j, k;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++){
            for (k=0;k<2;k++)
            for (j=0;j<3;j++)
                scanf("%lf",&D[i][k][j]);
        }
        double L = 0,R = 1000000,mid,ans = 0;
        int tim = 50;
        while(tim--&&L<R){
            mid = (L+R)/2;
            if (check(mid)) ans = mid,L = mid+eps;
            else R = mid-eps;
        }
        printf("%.3lf\n",ans);
    }
}

}}}

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

较裸的2-sat判定问题，二分了某个半径R后，可以根据是否会冲突决定建图，比如a组的0会碰到b组的1，那么建边就是a_0-->b_0

在建出的图上求强联通分量，如果a_0,a_1在同一强联通分量内，即false.

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
struct edges {
    int node, next;
} edge[400000], edge2[400000];
int node[1000], node2[1000], num, num2, belong[1000],Q[10000];
int N;
double D[500][2][3];
void add(int a, int b, edges *tmpedge, int *tmpnode, int &num) {
    tmpedge[num].node = b;
    tmpedge[num].next = tmpnode[a];
    tmpnode[a] = num++;
}
bool mark[1000];
int T[10000];
int Knum, Tnum;
void dfs1(int now) {  //?????DFS
    mark[now] = true;
    for (int i = node[now]; i != -1; i = edge[i].next)
        if (!mark[edge[i].node]) dfs1(edge[i].node);
    T[Tnum++] = now;
}
void dfs2(int now) {   //????????DFS
    belong[now] = Knum;
    mark[now] = true;
    for (int i = node2[now]; i != -1; i = edge2[i].next)
        if (!mark[edge2[i].node]) dfs2(edge2[i].node);
    return;
}
double sqr(double x){
    return x*x;
}
double eps = 1e-6;
double calcD(int i,int k1,int j,int k2){
    double ans = 0;
    for (int t=0;t<3;t++)
        ans+=sqr(D[i][k1][t]-D[j][k2][t]);
    return sqrt(ans);
}
bool check(double mid){
    int i,j,k1,k2;
        num = num2 = 0;
        memset(node, -1, sizeof (node));
        memset(node2, -1, sizeof (node2));
        for (i=0;i<N;i++)
            for (j=0;j<N;j++)
                if (i!=j){
                    for (k1 = 0;k1<2;k1++)
                        for (k2=0;k2<2;k2++){
                            if (calcD(i,k1,j,k2)<mid*2){
                                add(i*2+k1, j*2+1-k2, edge, node, num);
                                add(j*2+1-k2, i*2+k1, edge2, node2, num2);
                            }
                        }
                }
        Tnum = Knum = 0;
        memset(mark, false, sizeof (mark));
        for (i = 0; i < 2 * N; i++)
            if (!mark[i])
                dfs1(i);
        memset(mark, false, sizeof (mark));
        for (i = Tnum - 1; i >= 0; i--) {  //???????DFS
            if (!mark[T[i]])
            {
                Q[Knum] = T[i];        //????????????????
                dfs2(T[i]), Knum++;
            }
        }
        for (i=0;i<2*N;i+=2)
            if (belong[i]==belong[i+1])
            {
                return false;
            }
        return true;
}
int main() {
    int a, b, i, j, k;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++){
            for (k=0;k<2;k++)
            for (j=0;j<3;j++)
                scanf("%lf",&D[i][k][j]);
        }
        double L = 0,R = 1000000,mid,ans = 0;
        int tim = 50;
        while(tim--&&L<R){
            mid = (L+R)/2;
            if (check(mid)) ans = mid,L = mid+eps;
            else R = mid-eps;
        }
        printf("%.3lf\n",ans);
    }
}