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

AOJ 1064 Yanagi’s Comic

問題文: Yanagi’s Comic | Aizu Online Judge

UAPCの問題。とりあえず幾何かなとか思って避けてた人は問題文をしっかり読むべき。(自戒の意味を込めた)

実装方法をミスって悲惨な書き方しているけどいちおうソース。

再帰的にやると楽。忠実に実装した。

#include <iostream>
#include <complex>
#include <set>
#include <vector>
#define x(p) p.real()
#define y(p) p.imag() 

namespace std{
	bool operator < (const complex<int> &a,const complex<int> &b){
		return x(a) != x(b) ? x(a) < x(b) : y(a) < y(b);
	}
};
using namespace std;
typedef complex<int> P;
typedef pair<P,int> node;

P size[10];
P pos[10];

vector<int> used;

void search(set<node> K){
	while(!K.empty()){
		node get = *K.begin();
		K.erase(get);
		used.push_back(get.second);
		y(get.first) += y(size[get.second]);
		
		while(x(get.first) != 501){
			bool f = false;
			for(set<node>::iterator it = K.begin(); it != K.end() ; ++it){
				if( y((*it).first) < y(get.first) && y(get.first) < y((*it).first) + y(size[(*it).second]) && x((*it).first) == x(get.first) ){
					f = true; break;
				}
			}
			if(f) break;
			x(get.first)++;
		}
		
		set<node> R;
		for(set<node>::iterator it = K.begin(); it != K.end() ; ++it){
			if( y(get.first) >= y((*it).first) + y(size[(*it).second]) && x((*it).first)+x(size[(*it).second]) <= x(get.first) ){
				R.insert(*it);
			}
		}

		for(set<node>::iterator it = R.begin(); it != R.end() ; ++it)
			K.erase(*it);
		search(R);
	
	}
}
int main(){
	int n;
	int cnt = 0;
	while(cin >> n , n){
		used.clear();
		if(cnt++)cout << endl;
		for(int i = 0 ; i < n ; i++){
			int x1 , x2 , y1 , y2;
			cin >> x1 >> y1 >> x2 >> y2;
			if(x1 > x2) swap(x1,x2);
			if(y1 > y2) swap(y1,y2);
			pos[i]  = P(x1,y1);
			size[i] = P(x2-x1,y2-y1);
		}
		set<node> L;
		
		for(int i = 0 ; i < n ; i++)
			L.insert(make_pair(pos[i],i));
		
		search(L);
		
		int view[10] = {0};
		for(int i = 0 ; i < n ; i++)
			view[used[i]] = i+1;
		for(int i = 0 ; i < n ; i++)
			cout << view[i] << endl;
	}
}