Cod sursa(job #2061131)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 noiembrie 2017 22:26:48
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define Point pair<int,int>

using namespace std;

ifstream fin ("overlap.in");
ofstream fout ("overlap.out");

const int Nmax = 808;
int i, n;
map< Point, int > points;
map< Point, int > :: iterator it;
deque<int> q;
Point a[Nmax], b[Nmax];
bool used[Nmax];
int w[Nmax], go[Nmax];

Point add(Point a, Point b)
{
    return {a.x + b.x, a.y + b.y};
}

bool check(int id)
{
    int i, j, nr; bool ok;
    for(i=1; i<=n; ++i) b[i] = a[i];

    for(j=0; j<4; ++j)
    {
        memset(w, 0, sizeof(w));
        memset(used, 0, sizeof(used));
        w[1] = 1; w[id] = 2;

        for(i=2; i<=n; ++i)
            if(i != id)
            {
                b[i] = {-b[i].y, b[i].x};
                it = points.find(add(b[i], a[id]));
                if(it == points.end()) go[i] = 0;
                    else go[i] = it->second, used[it->second] = 1;
            }

        ok = 1;
        for(i=2; ok && i<=n; ++i)
            if(i != id && !used[i])
            {
                nr = i;
                while(nr && !w[nr])
                {
                    if(!go[nr] || w[go[nr]])
                    {
                        ok = 0;
                        break;
                    }
                    w[nr] = 1;
                    w[go[nr]] = 2;
                    nr = go[go[nr]];
                }
            }

        for(i=2; ok && i<=n; ++i)
            if(i != id && !w[i])
            {
                nr = i;
                while(nr && !w[nr])
                {
                    if(!go[nr] || w[go[nr]])
                    {
                        ok = 0;
                        break;
                    }

                    w[nr] = 1;
                    w[go[nr]] = 2;
                    nr = go[go[nr]];
                }
            }

        if(ok) return 1;
    }
    return 0;
}

int main()
{
    fin >> n;
    for(i=1; i<=n; ++i)
        fin >> a[i].x >> a[i].y;

    for(i=n; i; --i)
    {
        a[i].x -= a[1].x; a[i].y -= a[1].y;
        points[a[i]] = i;
    }

    for(i=2; i<=n; ++i) /// duc a[1] in a[i]
        if(check(i))
        {
            for(i=1; i<=n; ++i) fout << w[i] << '\n';
            return 0;
        }

    return 0;
}