読者です 読者をやめる 読者になる 読者になる

AOJ 0552 Exposition

問題文

Exposition | Aizu Online Judge

感想

かなり時間かけた。解けると嬉しいですねえ。問題文は日本語なので略。これが距離の総和とかだったらどうやって解くんだろう・・・。誰もブログに解法書いてくれないし情報オリンピックも解法公開しないし陰謀じゃないかと思いつつ解法書いてみる。

ヒント

JAPLJさんとこのマンハッタン距離の最遠点対についての説明

12/15-16 - TopCoderとJ言語と時々F#

(2点のマンハッタン距離) = |x1-x2| + |y1-y2|を場合分けしてうまく整理すると、

  • (x1+y1) + (-x1-y2)
  • (-x1+y1) + (x2-y2)
  • (x1-y1) + (-x2+y2)
  • (-x1-y1) + (x2+y2)

という式が出来上がって、本物のマンハッタン距離はこの中のいずれかが取る最大値(当然)。

この式が何を意味するかというと、一番上は、(x1+y1)が最大になるような点 と、(-x1-y2)が最大になるような点だけを探せばよくて、その下は(-x1+y1)が最大になる点と(x2-y2)が最大になるようなだけ点を探せば良い。(x+y)が最大になるような点とかはうまく管理してやる。

解法

↓反転

基本方針はpriority_queueを用いた貪欲。最大を最小化するので、最遠点対をできるだけ分けていく。

説明の簡単化のために、使ってない点の集合をS , 既に分けられた点が入っている2つの集合をA,Bとする。

  • 4つのpriority_queueを用意して、その中にそれぞれの点について、さっきの4通りの値をぶちこむ。要するに(x+y),(-x+y),(x-y),(-x-y)用のpriority_queue(使ってない点の集合S用)を作る。

  • その中から最大になるような組み合わせを選ぶんだけど、ここでSの中で距離が最大2点を選んで追加するとかやるのは嘘解法。なぜ問題かというと、既に分けられている点(A,Bに入っている点)のことを考えていないから。
  • そこでそれらことを考えてあげるために、A,B用のpriority_queueを2つさらに用意しておく。(2つの集合に分ける問題なので)
  • そうすると、『Sの中から2つ選び距離が最大になるような点』と『SとAで最大になるような点』と『SとBで最大になるような点』の3通りを考えれば良いことが分かる。後ろの2つは、SとAで最大になるならその点対のSの方をBに入れてやり、逆ならAに入れてやればよい。前者はどっちに入れたら距離が最小化されるか頑張ってシミュレーションして良い方につっこめば良い。

  • 最後に、A,Bそれぞれ2の集合の独立した点対の距離で最大のものを出力すれば良い。

ソース

死ぬほど汚い。無駄に関数ポインタとか使ってる・・・(本当に無駄)。

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#include <algorithm>
using namespace std;
#define INF (-(1<<29))
int A_(int x,int y){ return x+y; }
int B_(int x,int y){ return x-y; }
int C_(int x,int y){ return -x+y; }
int D_(int x,int y){ return -x-y; }
priority_queue< pair<int,int> > Q[3][4];
int (*f[4])(int x,int y) = {A_,B_,C_,D_};

pair<int,int> item[100000];

int used[100000];
int get(priority_queue< pair<int,int> > &A , priority_queue< pair<int,int> > &B){
	if(A.size() == 0 || B.size() == 0) return 0;
	//if(A.top().second == B.top().second) return INF;
	return A.top().first + B.top().first;
}



int get2(priority_queue< pair<int,int> > &A , int B){
	if(A.size() == 0) return 0;
	//if(A.top().second == B.top().second) return INF;
	return A.top().first + B;
}

int chk(int A,int B){
	if(Q[1][0].size()==0){
		return 0;
	}else{
		int ans = 0;
		ans = max( ans , get2(Q[1][0],f[3](item[A].first,item[A].second) ) );
		ans = max( ans , get2(Q[1][1],f[2](item[A].first,item[A].second) ) );
		ans = max( ans , get2(Q[2][0],f[3](item[B].first,item[B].second) ) );
		ans = max( ans , get2(Q[2][1],f[2](item[B].first,item[B].second) ) );
		return ans;
	}
}
int chkk(int A,priority_queue< pair<int,int> > R[4]){
	int ans = 0;
	ans = max( ans , get2(R[0],f[3](item[A].first,item[A].second) ) );
	ans = max( ans , get2(R[1],f[2](item[A].first,item[A].second) ) );
	return ans;
}
int put(int A,int B){
	if(A != -1) for(int j = 0 ; j < 4 ; j++) Q[1][j].push(make_pair(f[j](item[A].first,item[A].second),A));
	if(B != -1) for(int j = 0 ; j < 4 ; j++) Q[2][j].push(make_pair(f[j](item[B].first,item[B].second),B));
	if(A != -1) used[A] = true;
	if(B != -1) used[B] = true;
}

int main(){
	int n;
	cin >> n;
	
	for(int i = 0 ; i < n ; i++){
		int x,y;
		cin >> x >> y;
		item[i] = make_pair(x,y);
		for(int j = 0 ; j < 4 ; j++){
			Q[0][j].push(make_pair(f[j](x,y),i));
		}
	}
	//int lastDistance;
	while(Q[0][0].size()){
		int sub = -1 , h = -1 , aa , bb;
		for(int i = 0 ; i < 3 ; i++){
			for(int j = 0 ; j < 4 ; j++){
				int r = get( Q[0][j] , Q[i][3-j] );
				if( r > sub){
					sub = r;
					h = i;
					aa = Q[0][j].top().second;
					bb = Q[i][3-j].top().second;
				}
			}
		}
		if(h==0){
			if( max( chkk(aa,Q[1]) , chkk(bb,Q[2]) ) > max( chkk(aa,Q[2]) , chkk(bb,Q[1]) ) ){
				put(bb,aa);
			}else{
				put(aa,bb);
			}
		}else if(h==1){
			put(-1,aa);
		}else{
			put(aa,-1);
		}
		
		for(int i = 0 ; i < 4 ; i++){ while(Q[0][i].size() && used[Q[0][i].top().second]) Q[0][i].pop(); }
	}
	int ans = 0;
	for(int i = 1 ; i < 3 ; i++){
		for(int j = 0 ; j < 4 ; j++){
			int r = get( Q[i][j] , Q[i][3-j] );
			ans = max( ans , r );
		}
	}	
	cout << ans  << endl;
}