Cod sursa(job #13474)

Utilizator devilkindSavin Tiberiu devilkind Data 6 februarie 2007 19:49:18
Problema Overlap Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <stdio.h>
#include <string.h>
#define modulo 666013
#define NMAX 801

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+1;
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;
}