Cod sursa(job #841844)

Utilizator stoicatheoFlirk Navok stoicatheo Data 25 decembrie 2012 10:26:56
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define Nmax 810

int n, i, j, k, ShX, ShY, p, q, poz, ok, par;
struct punct{ int x; int y; } a[Nmax], init[Nmax];
int fol[Nmax], v[Nmax], sol[Nmax], afis[Nmax];

inline int cmp(punct a, punct b)
{
    if (a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

void cit()
{
    freopen("overlap.in", "r", stdin);
    freopen("overlap.out", "w", stdout);

    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].x, &a[i].y);
        init[i] = a[i];
    }

    sort(a + 1, a + n + 1, cmp);
}

void rotesc(int k)
{
    if (k == 0) return;
    if (k != 0)
    {
        int x = p, y = q;

        if (k == 1) {p = y; q = -x;}
        if (k == 2) {p = -x; q = -y;}
        if (k == 3) {p = -y; q = x;}
    }
}

int caut(int p, int q)
{
    int st = 0, dr = n + 1, r = 0;
    while (st + 1 < dr)
    {
        r = (st + dr) / 2;

        if (a[r].x > p) dr = r;
        else if (a[r].x < p) st = r;
             else if (a[r].x == p)
             {
                    if (a[r].y > q) dr = r;
                    else if (a[r].y < q) st = r;
                         else if (fol[r] == 0) return r;
                              else return -1;
                  }
    }
    return -1;
}

int verif_ok()
{
    ok = 1;
    for (int i = 1; i <= n; i++)
        if (fol[i] == 0) ok = 0;
        else fol[i] = 0;
    fol[0] = 1;
    for (int i = 1; i <= n; i++)
        if (fol[i] == 0 && v[i] != 0)
        {
            j = i; par = 0;
            while (fol[j] == 0)
            {
                par++; fol[j] = 1;
                sol[j] = par % 2 + 1;
                j = v[j];
            }
            if (par % 2 == 1) ok = 0;
        }

    return ok;
}

void solve()
{
    for (k = 0; k <= 4; k++)
    {
        for (i = 2; i <= n; i++)
        {
            p = a[1].x; q = a[1].y;
            rotesc(k);

            for (j = 0; j <= n; j++) v[j] = fol[j] = 0;
            fol[1] = 1; v[1] = i;

            fol[i] = 1;
            ShX = a[i].x - p;
            ShY = a[i].y - q;

            for (j = 2; j <= n; j++)
                if (fol[j] == 0)
                {
                    p = a[j].x; q = a[j].y;
                    rotesc(k);

                    p = p + ShX;
                    q = q + ShY;

                    poz = caut(p, q);
                    if (poz > 0)
                    {
                        fol[poz] = fol[j] = 1;
                        v[j] = poz;
                    }
                }

            if (verif_ok()) return;
        }
    }
}

void write()
{
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (init[j].x == a[i].x && init[j].y == a[i].y)
                afis[j] = sol[i];
    for (i = 1; i <= n; i++)
        printf("%d\n", afis[i]);
}

int main()
{

    cit();
    solve();
    write();

    return 0;
}