CF85 E Guard Towers——二分图

题目：http://codeforces.com/contest/85/problem/E

给定一些点的坐标，求把它们分成两组，组内最大距离的最小值；

二分答案，判断就是看距离大于 mid 的点能否组成二分图，若能组成则可行，2^(连通块个数)就是方案数；

n^2 连边果然会超时...直接在 dfs 里判断距离就好了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

int const maxn=,mod=1e9+;

int n,x[maxn],y[maxn],ans,col[maxn],cnt,hd[maxn],ct,num;

bool vis[maxn];

//struct N{

//    int to,nxt;

//    N(int t=0,int n=0):to(t),nxt(n) {}

//}ed[maxn*maxn];

//void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}

int calc(int i,int j){return abs(x[i]-x[j])+abs(y[i]-y[j]);}

bool dfs(int x,int mid)

{

    vis[x]=;

//    for(int i=hd[x],u;i;i=ed[i].nxt)

    for(int u=;u<=n;u++)

    {

        if(calc(x,u)<=mid||u==x)continue;

        if(vis[u])

        {

            if(col[u]==col[x])return ;

            continue;

        }

        col[u]=!col[x];

        if(dfs(u,mid))return ;

    }

    return ;

}

bool ck(int mid)

{

    cnt=;

//    ct=0;

//    memset(hd,0,sizeof hd);

//    memset(col,0,sizeof col);

    memset(vis,,sizeof vis);

//    for(int i=1;i<=n;i++)

//        for(int j=i+1;j<=n;j++)

//            if(calc(i,j)>mid)add(i,j),add(j,i);

    for(int i=;i<=n;i++)

        if(!vis[i])

        {

            if(dfs(i,mid))return ;

            cnt++;

        }

    return ;

}

ll pw(ll a,int b)

{

    ll ret=;

    for(;b;b>>=,a=(a*a)%mod)

        if(b&)ret=(ret*a)%mod;

    return ret;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d",&x[i],&y[i]);

    int l=,r=;

    while(l<=r)

    {

        int mid=((l+r)>>);

        if(ck(mid))ans=mid,num=cnt,r=mid-;

        else l=mid+;

    }

    printf("%d\n%I64d\n",ans,pw(,num));

    return ;

}