Cod sursa(job #2074230)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 24 noiembrie 2017 11:33:27
Problema Overlap Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=1004;
struct point
{
    int x;
    int y;
    bool operator <(const point &aux) const
    {
        if(x!=aux.x) return (x<aux.x);
        return y<aux.y;
    }
}v[nmax],v2[nmax];
map<point,int>ap;
int n;
int p[nmax],p2[nmax],val[nmax],vis[nmax];
inline void citeste()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        ap[v[i]]=i;
    }
}
point rotate_90(point a)
{
    point b;
    b.x=-a.y;
    b.y=a.x;
    return b;
}
int dfs(int nod,int vlt)
{
    vis[nod]=1;
    if(val[nod]==0)
    {
        val[nod]=vlt;
        if(p[nod]!=-1) return dfs(p[nod],3-vlt);
        else
        {
            if(vlt==1) return 0;
            return 1;
        }
    }
    else
    {
        if(val[nod]!=vlt) return 0;
        return 1;
    }
}
int try_for(int rot,int transx,int transy)
{
    for(int i=1;i<=n;i++)
    {
        val[i]=0;
        vis[i]=0;
        v2[i]=v[i];
        for(int j=1;j<=rot;j++) v2[i]=rotate_90(v2[i]);
        v2[i].x+=transx;
        v2[i].y+=transy;
        if(ap[v2[i]]==0) p[i]=-1;
        else p[i]=ap[v2[i]];
    }
    int as=0;
    for(int i=1;i<=n;i++)
    {
        if(p[i]==-1) continue;
        if(!vis[i])
        {
            if(dfs(i,1)==0)
            {
               // if(transx==11&&transy==-2) printf("!%d!",i);
                as=1;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) return 0;
    as=1-as;
    return as;
}
void print_solution()
{
    for(int i=1;i<=n;i++) printf("%d\n",val[i]);
}
inline void do_for_rotation_and_translation()
{
    point temp=v[1];
    for(int j=1;j<=3;j++)
    {
        temp=rotate_90(temp);
        for(int i=1;i<=n;i++)
        {
            if(try_for(j,v[i].x-temp.x,v[i].y-temp.y))
            {
                print_solution();
                return;
            }
        }
    }
}
int main()
{
    freopen ("overlap.in","r",stdin);
    freopen ("overlap.out","w",stdout);
    citeste();
    do_for_rotation_and_translation();
}