Pagini recente » Cod sursa (job #3286266) | Cod sursa (job #317785) | Cod sursa (job #498104) | Cod sursa (job #313662) | Cod sursa (job #822422)
Cod sursa(job #822422)
// 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 A[dim][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.y;
w.y=-e.x;
}
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;
A[v[i].x][v[i].y]=i;
}
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)!=harta.end()){
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[A[v[i].x][v[i].y]]<<"\n";
}
break;
}
}
return 0;
}