Cod sursa(job #2074576)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 24 noiembrie 2017 19:43:15
Problema Overlap Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <bits/stdc++.h>

using namespace std;

FILE *in,*out;

const int nmax = 805;

int n;

struct Point
{
    int x,y;
}v[nmax];

struct Triplet
{
    int rot,tx,ty;
    bool operator< (const Triplet &other) const
    {
        if(rot!=other.rot)
            return rot < other.rot;
        if(tx!=other.tx)
            return tx<other.tx;
        return ty<other.ty;
    }
};

struct Pereche
{
    int a,b;
};

map <Triplet, int> find_list;

vector<Pereche> lista[nmax*nmax];
int last_list;

void translatie(Point a, Point b,int &tx,int &ty)
{
    tx = b.x - a.x;
    ty = b.y - a.y;
}

void add(int k,int l,int tx,int ty,int r)
{
    Triplet tmp = {r,tx,ty};
    Pereche tmp2 = {k,l};


        //cerr<<r<<" "<<tx<<" "<<ty<<"\n";

    if(find_list[tmp] == 0)
    {
        find_list[tmp] = ++last_list;
    }

    //cerr<<find_list[tmp]<<"\n";
    lista[find_list[tmp]].push_back(tmp2);
}

void rotatie(Point &p)
{
    int aux = p.x;
    p.x = -p.y;
    p.y = aux;
}

int dest[nmax];
bool visited[nmax];
int grad[nmax];

bool dfs(int i,int len = 0)
{
    if(visited[i]==1) //am terminat ciclul
    {
        return (len%2) == 0;

    }
    visited[i]=1;

    if(dest[i] == 0)
    {
        return (len%2) ==1;
    }

    dfs(dest[i], len+1);
}

int rez[nmax];

void dfs2(int i,int len = 0)
{
    if(visited[i]==1) //am terminat ciclul
    {
        return;

    }
    visited[i]=1;

    if(dest[i] == 0)
    {
        return;
    }
    rez[i]=len%2+1;
    dfs2(dest[i], len+1);
}

bool verifica(vector <Pereche> t)
{
    //for(int i = 0;i < t.size();i ++)
        //fprintf(out,"%d %d\n",t[i].a,t[i].b);
    //fprintf(out,"\n");
    memset(dest,0,sizeof dest);
    memset(visited,0,sizeof visited);
    for(int i = 0;i < t.size();i ++)
    {
        assert(dest[t[i].a]==0);//crapa daca nu e 0
        dest[t[i].a] = t[i].b;
        grad[t[i].b] ++;
    }
    for(int i = 1;i <= n;i ++)
    {
        if(visited[i] == 0)
            if(grad[i] == 0)
                if(dfs(i) == 0)
                    return 0;
    }
    if(dfs[1] == 0)
        return 0;
    return 1;
}

void afisare()
{
    memset(visited,0,sizeof visited);
    for(int i = 1;i <= n;i ++)
    {
        if(grad[i] == 0 && visited[i] == 0)
            dfs2(i);
    }
    for(int i = 1;i <= n;i ++){
        if(rez[i] == 0)
            rez[i] = 2;
        fprintf(out,"%d\n",rez[i]);
    }
}

int main()
{
    in = fopen("overlap.in","r");
    out =fopen("overlap.out","w");
    fscanf(in,"%d",&n);
    for(int i = 1;i <= n;i ++)
        fscanf(in,"%d %d",&v[i].x,&v[i].y);
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            if(i==j)
                continue;
            Point aux = v[i];
            for(int r = 0;r < 4;r ++)
            {
                int tx,ty;
                translatie(aux,v[j],tx,ty);
                add(i,j,tx,ty,r);
                rotatie(aux);
            }
        }
    }
    for(int i = 1;i <= last_list;i ++)
    {
        if(lista[i].size() >= (n/2))
        {
            if(verifica(lista[i]) == 1)
            {
                afisare();
                return 0;
            }
        }
    }
    return 0;
}