Cod sursa(job #2061087)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 noiembrie 2017 22:02:19
Problema Overlap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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, shiftX, shiftY, w[Nmax];

map< Point, int > points, s, ss;
deque<int> q;
Point a[Nmax], b[Nmax];

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

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

    for(j=0; j<4; ++j)
    {
        memset(w, 0, sizeof(w));
        q.clear(); s.clear(); ss.clear();

        int nr = n - 2;
        for(i=2; i<=n; ++i)
        if(i != id)
        {
            c = {-b[i].y, b[i].x};
            b[i] = c;
            if(points.find(add(b[i], a[id])) == points.end()) q.push_back(i);
                else s[add(b[i], a[id])] = i;

            ss[b[i]] = i;
        }

        while(q.size())
        {
            int x = q.front();
            q.pop_front();
            if(w[x]) continue;

            if(!s[a[x]]) break;
            w[x] = 2;
            w[s[a[x]]] = 1;

            c = a[s[a[x]]];
            if(ss.find(c) != ss.end()) q.push_front(ss[c]);

            nr -= 2;
        }

        if(!nr) 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))
        {
            w[1] = 1; w[i] = 2;
            for(i=1; i<=n; ++i) fout << w[i] << '\n';
            return 0;
        }

    return 0;
}