team2012-F3-sol-0014

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一个空间区域和n组点，每组两个点只能选一个且必须选一个，求满足此约束下的最近点对的距离最大值。
解法：首先二分这个最小距离，那么某两个点就不能同时选择，这是一个2-SAT的判定问题
当group[i][1]和group[j][1]冲突时，给group[i][1]连接一条边到group[j][2]，group[j][1]连接一条边到group[i][2]。其余类推，得到一个有向图
求这个有向图中的所有强连通分量，若某组group[k][1]和group[k][2]在一个强连通分量里，则无法满足此约束。
反之若每组的两个元素都在不同的强连通分量里，可以满足此约束。
P.S. rejudge以后，输出的时候要处理下
}}}
{{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

const int MAXN = 402;
int n, N, cnt, ok, x[MAXN], y[MAXN], z[MAXN],
    num[MAXN], low[MAXN];
double dis[MAXN][MAXN];
vector<int> conn[MAXN];
bool vis[MAXN];
stack<int> stk;
bool instk[MAXN], chk[MAXN];

void dfs(int x)
{
    vis[x] = 1;
    num[x] = low[x] = ++cnt;
    stk.push(x);
    instk[x] = 1;
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(!vis[v])
        {
            dfs(v);
            if(low[x] > low[v]) low[x] = low[v];
        }
        else if(instk[v])
            if(low[x] > low[v]) low[x] = low[v];
    }
    if(low[x] == num[x])
    {
        memset(chk, 0, sizeof(chk));
        int w;
        do
        {
            w = stk.top();
            stk.pop();
            instk[w] = 0;
            chk[w] = 1;
        }while(w != x);

        for(int i=1;i<N;i+=2)
            if(chk[i] && chk[i+1])
                ok = 0;
    }
}

bool test(double mind)
{
    for(int i=1;i<=N;i++)
        conn[i].clear();
    for(int i=1;i<=N;i++)
        for(int j=i+1+(i&1);j<=N;j++)
            if(dis[i][j] < mind)
            {
                int ii, jj;
                if(i&1) ii = i+1;
                else  ii = i-1;
                if(j&1) jj = j+1;
                else  jj = j-1;
                conn[i].push_back(jj);
                conn[j].push_back(ii);
            }

    memset(vis, 0, sizeof(vis));
    ok = 1;
    for(int i=1;i<=N;i++)
        if(!vis[i])
        {
            dfs(i);
            if(!ok)
                return 0;
        }
    return 1;
}

double gao()
{
    double low = 0, high = 1e8;
    int cs = 100;
    while(cs--)
    {
        double mid = (low+high) / 2;
        if(test(mid))
            low = mid;
        else
            high = mid;
    }
    return low/2;
}

double cal_dis(int i, int j)
{
    double dx = x[i]-x[j],
           dy = y[i]-y[j],
           dz = z[i]-z[j];
    return sqrt(dx*dx+dy*dy+dz*dz);
}

int main()
{
    while(cin>>n)
    {
        N = n*2;
        for(int i=1;i<=N;i++)
            cin>>x[i]>>y[i]>>z[i];
        for(int i=1;i<=N;i++)
            for(int j=i+1;j<=N;j++)
                dis[i][j] = cal_dis(i, j);
        cout.precision(3);
        cout<<fixed<<floor(gao()*1000)/1000.0<<endl;
    }
    return 0;
}
}}}

题意：给定一个空间区域和n组点，每组两个点只能选一个且必须选一个，求满足此约束下的最近点对的距离最大值。
解法：首先二分这个最小距离，那么某两个点就不能同时选择，这是一个2-SAT的判定问题
当group[i][1]和group[j][1]冲突时，给group[i][1]连接一条边到group[j][2]，group[j][1]连接一条边到group[i][2]。其余类推，得到一个有向图
求这个有向图中的所有强连通分量，若某组group[k][1]和group[k][2]在一个强连通分量里，则无法满足此约束。
反之若每组的两个元素都在不同的强连通分量里，可以满足此约束。
P.S. rejudge以后，输出的时候要处理下

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 402;
int n, N, cnt, ok, x[MAXN], y[MAXN], z[MAXN],
    num[MAXN], low[MAXN];
double dis[MAXN][MAXN];
vector<int> conn[MAXN];
bool vis[MAXN];
stack<int> stk;
bool instk[MAXN], chk[MAXN];
void dfs(int x)
{
    vis[x] = 1;
    num[x] = low[x] = ++cnt;
    stk.push(x);
    instk[x] = 1;
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(!vis[v])
        {
            dfs(v);
            if(low[x] > low[v]) low[x] = low[v];
        }
        else if(instk[v])
            if(low[x] > low[v]) low[x] = low[v];
    }
    if(low[x] == num[x])
    {
        memset(chk, 0, sizeof(chk));
        int w;
        do
        {
            w = stk.top();
            stk.pop();
            instk[w] = 0;
            chk[w] = 1;
        }while(w != x);
        for(int i=1;i<N;i+=2)
            if(chk[i] && chk[i+1])
                ok = 0;
    }
}
bool test(double mind)
{
    for(int i=1;i<=N;i++)
        conn[i].clear();
    for(int i=1;i<=N;i++)
        for(int j=i+1+(i&1);j<=N;j++)
            if(dis[i][j] < mind)
            {
                int ii, jj;
                if(i&1) ii = i+1;
                else  ii = i-1;
                if(j&1) jj = j+1;
                else  jj = j-1;
                conn[i].push_back(jj);
                conn[j].push_back(ii);
            }
    memset(vis, 0, sizeof(vis));
    ok = 1;
    for(int i=1;i<=N;i++)
        if(!vis[i])
        {
            dfs(i);
            if(!ok)
                return 0;
        }
    return 1;
}
double gao()
{
    double low = 0, high = 1e8;
    int cs = 100;
    while(cs--)
    {
        double mid = (low+high) / 2;
        if(test(mid))
            low = mid;
        else
            high = mid;
    }
    return low/2;
}
double cal_dis(int i, int j)
{
    double dx = x[i]-x[j],
           dy = y[i]-y[j],
           dz = z[i]-z[j];
    return sqrt(dx*dx+dy*dy+dz*dz);
}
int main()
{
    while(cin>>n)
    {
        N = n*2;
        for(int i=1;i<=N;i++)
            cin>>x[i]>>y[i]>>z[i];
        for(int i=1;i<=N;i++)
            for(int j=i+1;j<=N;j++)
                dis[i][j] = cal_dis(i, j);
        cout.precision(3);
        cout<<fixed<<floor(gao()*1000)/1000.0<<endl;
    }
    return 0;
}