Pagini recente » Cod sursa (job #2353207) | Cod sursa (job #2973825) | Cod sursa (job #1225388) | Cod sursa (job #2207988) | Cod sursa (job #13491)
Cod sursa(job #13491)
#include <stdio.h>
#include <string.h>
#define modulo 666013
#define NMAX 80001
FILE *f = fopen("overlap.in","rt"), *g = fopen("overlap.out","wt");
struct pct{long int x,y;} a[NMAX],rot[NMAX];
struct hash{long int x,y,poz;
hash *urm;} *vf[modulo];
long int i,j,k,n,shx,shy,mul[NMAX],h[NMAX],cmax;
void citire()
{
long int x,y,val;
hash *p;
fscanf(f,"%ld",&n);
for (i=1;i<=n;i++)
{
fscanf(f,"%ld %ld",&x,&y);
a[i].x=x;
a[i].y=y;
if (x>cmax) cmax=x;
if (y>cmax) cmax=y;
rot[i].x=x;
rot[i].y=y;
val=x%modulo;
p=new hash;
p->x=x;
p->y=y;
p->poz=i;
p->urm=vf[val];
vf[val]=p;
}
}
int check()
{
long int x,y,val,ok;
hash *p;
for (i=2;i<=n;i++)
{
memset(h,0,sizeof(h));
shx=rot[i].x-a[1].x;
shy=rot[i].y-a[1].y;
h[1]=h[i]=1;
mul[1]=0;mul[i]=1;
ok=1;
for (j=2;j<=n;j++)
if (!h[j])
{
x=a[j].x+shx;
y=a[j].y+shy;
val=x%modulo;
p=vf[val];
while (p)
{
if (p->x==x&&p->y==y&&p->poz!=j) {h[p->poz]=1;mul[p->poz]=1;
h[j]=1;h[p->poz]=1;mul[j]=0;
break;}
p=p->urm;
}
}
for (j=1;j<=n;j++)
if (!h[j]) {ok=0;break;}
if (ok) {for (j=1;j<=n;j++)
fprintf(g,"%ld\n",mul[j]+1);
return 1;}
}
return 0;
}
void rotate()
{long int x,y,val;
for (i=1;i<=n;i++)
{
x=rot[i].x;y=rot[i].y;
rot[i].x=cmax-y;
rot[i].y=x;
}
hash *p;
/*for (i=1;i<=n;i++)
while (vf[i])
{
p=vf[i];
vf[i]=vf[i]->urm;
delete p;
}*/
for (i=1;i<=n;i++)
vf[i]=NULL;
for (i=1;i<=n;i++)
{
x=rot[i].x;
y=rot[i].y;
val=x%modulo;
p=new hash;
p->x=x;
p->y=y;
p->poz=i;
p->urm=vf[val];
vf[val]=p;
}
}
int main()
{
long int k,ok=0;
citire();
for (k=0;(k<=3)&&(!ok);k++)
{
ok=check();
rotate();
if (ok) {fclose(f);fclose(g);return 0;}
}
fprintf(g,"-1");
fclose(f);
fclose(g);
return 0;
}