Cod sursa(job #774095)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 3 august 2012 14:20:25
Problema Overlap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <map>

using namespace std;

#define maxn 880

int n;
int s[maxn];
pair<int, int> v[maxn];
map<pair<int, int>, int> mp;

void solve()
{
    int x1=v[1].first, y1=v[1].second;
    int xs, ys, nc;
    pair<int, int> p;

    for(int pas=0; pas<4; ++pas)
    {
        for(int i=1; i<=n; ++i)
        {
            if(pas==0)
                continue;

            xs=v[i].first-x1;
            ys=v[i].second-y1;

            nc=0;
            for(int j=1; j<=n; ++j)
            {
                p=make_pair(v[j].first-xs, v[j].second-ys);
                if(mp[p]!=0)
                {
                    s[j]=2;
                    s[mp[p]]=1;
                    ++nc;
                }
            }

            if(nc==n/2)
                return;
        }

        for(int i=1; i<=n; ++i)
        {
            xs=v[i].second;
            ys=-v[i].first;
            v[i].first=xs;
            v[i].second=ys;
        }
    }
}


int main()
{
    freopen("overlap.in", "r", stdin);
    freopen("overlap.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d", &v[i].first, &v[i].second);
        mp[v[i]]=i;
    }

    solve();

    for(int i=1; i<=n; ++i)
        printf("%d\n", s[i]);

    return 0;
}