Cod sursa(job #822276)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 23 noiembrie 2012 06:10:20
Problema Overlap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
// sursa teste
#include<fstream>
#include<map>
#include<cstring>
#define dim 810
using namespace std;


ifstream f("overlap.in");
ofstream g("overlap.out");
int viz[dim];
int shiftx,shifty,i,j,n;
struct pct{
	int x,y;
};
pct v[dim],v2[dim];
bool operator< ( const pct &a, const pct &b ) { return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x); }
// functie rotire 
pct rotire(pct e,int k) {
	pct w;
	w.x=e.x;
	w.y=e.y;
	if(k==1){
		w.x=-e.y;
		w.y=e.x;
	}
	if(k==3){
		w.x=e.x;
		w.y=-e.y;
	}
	if(k==2){
		w.x=-e.x;
		w.y=-e.y;
	}
	return w;
}
map <pct,int> harta;
int cmp (pct a,pct b){
	if(a.x==b.x)
		return a.y<b.y;
	else
		return a.x<b.x;
}
int main () {
	
	f>>n;
	
	for(i=1;i<=n;++i){
		
		f>>v[i].x>>v[i].y;
		
	}
	
	sort(v+1,v+1+n,cmp);
	for(i=1;i<=n;++i		)
		harta[v[i]]=i;
	for(int rot=0;rot<=3;++rot) {
		//rotim punctile cu rot*90 grade
		for(i=1;i<=n;++i)
			v2[i]=rotire(v[i],rot);
		
		for(j=2;j<=n;++j ) {
			
			memset(viz,0,sizeof(viz));
			//cautam constantele de translatie
			shiftx=v[j].x-v2[1].x;
			shifty=v[j].y-v2[1].y;
			//marcam folosirea celor 2 pct
			viz[1]=1;
			viz[j]=2;
			pct pn;
			for(i=2;i<=n;++i){
				
				if(viz[i])//trecem la pasul urmator daca punctul v2[i] a fost folosit
					continue;
				pn.x=v2[i].x+shiftx;
				pn.y=v2[i].y+shifty;
				//verificam daca punctul pn apartine hartii.daca nu apartine il inseram pe i in multimea 1 si pn in multimea 2
				if(harta.find(pn)!=0){
					viz[i]=1;
					viz[harta[pn]]=2;
				}
			}
		}
		
		//Presupunem ca avem create cele doua multimi
		int a=1;
		for(i=1;i<=n;++i)
			if(viz[i]==0){
				a=0;
				
			}
		if(a==1){
			for(i=1;i<=n;++i)
				g<<viz[i]<<"\n";
			break;
		}
	}
	return 0;
}