2013-12-25

■ JOI Exposition 02:47

この問題だけ妙にGoogleでヒットしないのでまじめに書きます

概要:

N(<=10^5)個の点が2次元空間に存在している。

頂点を2集合に分けることで

それぞれの集合内の2点間のマンハッタン距離の最大値を最小化せよ.

解法:

とりあえず、(x,y)->(x+y,x-y)という座標変換を行うと

変換後の2点において、max(x座標の差,y座標の差)がマンハッタン距離（http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2)

になることを各自で確認してください。(自明なはずです)

で、"最大値を最小化"という問題なので二分探索が使えるのではないか？と考えられます。

次に各集合内での最小のマンハッタン距離がv以下にできるかということは

変換後の座標上で、v*vの正方形2枚で全点覆えるかと同値である(ここ大事)ので

xmin,xmax,ymin,ymaxを変換後の座標でのx,y座標の最小最大、とすると

(i) v>=min(xmax-xmin,ymax-ymin)の場合

最大最小の差が小さいほうの値は無視出来るので、

もう一方の値すべてを長さvの2線分で覆うことができるかを確かめればよく、二分探索を用いればO(log n)でできます。

(ii)そうでない場合

このとき、2枚の正方形のおき方は

・左上が(xmin,ymax)の物と右下が(xmax,ymin)の物

・左下が(xmin,ymin)の物と右上が(xmax,ymax)の物

の2通りしかありません。(これも各自で確認してください、自明です)

こちらもそれぞれ二分探索を行えばO(N log N)でできます。

以上よりO(N log^2 N)でできます。

この(x,y)->(x+y,x-y)の変換を知らなければ絶対に(よほどの天才を除く)解けないので、

これから先も覚えていましょう。

最後にコードを乗せるので、がんばって理解してください。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
#define geta 200000
vector<int>za[400005];
vector<int>all;
int main()
{
	int n;
	scanf("%d",&n);
	P p[100005];
	//上の解説内と同じ意味
	int xmin=INF,xmax=-INF,ymin=INF,ymax=-INF;
	for(int i=0;iint x,y;
		scanf("%d %d",&x,&y);
		//座標変換する
		p[i]=mp(x+y,x-y);
		xmin=min(xmin,x+y);
		xmax=max(xmax,x+y);
		ymin=min(ymin,x-y);
		ymax=max(ymax,x-y);
	}
	//簡単のため、変換後の座標でxmax-xmin
	//つまり必ずmin(xmax-xmin,ymax-ymin)=ymax-yminになる
	if(xmax-xminfor(int i=0;i//y座標ごとにx座標を管理する。ただしy座標が負だとまずいので下駄を履かせる(+200000して0以上にする)。
	//allはすべてのx座標を持つ。
	for(int i=0;i//二分探索用にソート
	sort(all.begin(),all.end());
	for(int  i=0;i<400005;i++) sort(za[i].begin(),za[i].end());
	//二分探索の上限下限
	int lb=0;
	int ub=xmax-xmin;
	//y座標のmaxmin間の差(min(xmax-xmin,ymax-ymin)と等しい)
	//これで場合わけする
	int ano=ymax-ymin;
	while(ub-lb>1)
	{
		int mid=(lb+ub)>>1;
		if(mid>=ano)
		{
			//y座標は無視.x座標だけ見る。
			int d=upper_bound(all.begin(),all.end(),all[0]+mid)-all.begin();
			if(d==all.size() || all[all.size()-1]-all[d]<=mid) ub=mid;
			else lb=mid;
		}
		else
		{
			//y座標ごとにみる。
			
			//左上が(xmin,ymax)の物と右下が(xmax,ymin)の物

			//左の正方形だけで覆うべき範囲
			for(int i=ymax+geta;i>ymin+mid+geta;i--)
			{
				if(za[i].empty())  continue;
				if(za[i][za[i].size()-1]>xmin+mid) goto next;
			}
			//右の正方形だけで覆うべき範囲
			for(int i=ymin+geta;iif(za[i].empty())  continue;
				if(za[i][0]goto next;
			}
			//両方の正方形のどちらかで覆えればよい
			for(int i=ymax-mid+geta;i<=ymin+mid+geta;i++)
			{
				if(za[i].empty())  continue;
				int d=upper_bound(za[i].begin(),za[i].end(),xmin+mid)-za[i].begin();
				int e=lower_bound(za[i].begin(),za[i].end(),xmax-mid)-za[i].begin();
				if(dgoto next;
			}
			//ここにいるなら解はmid以下
			ub=mid;
			continue;
			next:;
			
			//左下が(xmin,ymin)の物と右上が(xmax,ymax)の物

			//右の正方形だけで覆うべき範囲
			for(int i=ymax+geta;i>ymin+mid+geta;i--)
			{
				if(za[i].empty())  continue;
				if(za[i][0]goto next2;
			}
			//左の正方形だけで覆うべき範囲
			for(int i=ymin+geta;iif(za[i].empty())  continue;
				if(za[i][za[i].size()-1]>xmin+mid) goto next2;
			}
			//両方の正方形のどちらかで覆えればよい
			for(int i=ymax-mid+geta;i<=ymin+mid+geta;i++)
			{
				if(za[i].empty())  continue;
				int d=upper_bound(za[i].begin(),za[i].end(),xmin+mid)-za[i].begin();
				int e=lower_bound(za[i].begin(),za[i].end(),xmax-mid)-za[i].begin();
				if(dgoto next2;
			}
			//ここにいるなら解はmid以下
			ub=mid;
			continue;
			next2:;
			//ここなら解はmidより大
			lb=mid;
		}
	}
	printf("%d\n",ub);
}

ツイートする