#C240218C. 塔

标签（Label）

• 二分图匹配
• 二分答案

前言（Front talk)

$\qquad$由于题目中 $n$ 给的是 $5000$ ，所以根本没有往 $O(n^2logn)$ 的时间复杂度去想，结果……

$\qquad$数据太水，正解就是 $O(n^2logn)$。(* ￣︿￣)

网址（Website）

题目详情 - 塔 - Super

题解 - 塔 - Super

题解（Solution）

$\qquad$ 由于出现最大和最小，第一时间就想到了二分答案，但是考试时认为 $O(n^2logn)$ 过不了 ，所以就根本没在往后面想了。

$\qquad$ 计算得可以直接求出每两个塔之间的距离，并且存下来。

$\qquad$ 二分中的 $mid$ 是两组塔距离的上限，如果两塔之间的距离大于 $mid$ ，那么这两个塔一定不在同一个组内，于是可以将两个塔的编号连边。由于只有两个组，我们可以用二分图的判定来判断此时的 $mid$ 是否满足条件。

$\qquad$ 由于当前的二分图不一定是全联通，因此这个联通块里面的塔可以放在左边或者放在右边，因此最后的方案数就是2的连通块个数次方。

代码（Code）

#include<bits/stdc++.h>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 5005;

bool ST;

int d[N][N];
int n,ans;
P tow[N];

int col[N],sum;
bool check(int mid){
	memset(col,0,sizeof col);
	queue<int> q;sum=0;
	For(i,1,n){
		if(col[i]) continue;
		q.emplace(i);col[i]=1;
		while(q.size()){
			int x=q.front();q.pop();
			For(y,1,n){
				if(d[x][y]<=mid) continue;
				
				if(col[y]==col[x]){
					return false;
				}else if(!col[y]) col[y]=3-col[x],q.emplace(y);
			}
		}sum++;
	}return true;
}

inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod,k>>=1;
	}return res;
}

bool ED;
inline int get_dis(P x,P y){return abs(x.first - y.first) + abs(x.second - y.second);}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("tower");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	cin>>n;int Tim = clock();
	For(i,1,n) tow[i]={input(),input()};
	
	{//求得每个点之间的距离 
		For(i,1,n) For(j,1,n){
			d[i][j] = get_dis(tow[i],tow[j]);
		}
	}
	
	{//二分求得最小距离 
		int l=0,r=10000,mid;
		while(l<=r){
			mid = (l+r)>>1;
			if(check(mid)) r=mid-1,ans=mid;
			else l=mid+1;
		}check(ans);
	}
	
	cout<<ans<<'\n'<<ksm(2,sum)<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}