Cod sursa(job #2006301)

Utilizator lflorin29Florin Laiu lflorin29 Data 29 iulie 2017 13:35:36
Problema Overlap Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 802;

int n;

struct Point
{
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {};
    Point rotated(int degrees)
    {
        long double dg = (long double)degrees * acos(-1) / 180.0;
        int Cos = cos(dg), Sin = sin(dg);
        return Point(x * Cos - y * Sin, x * Sin + y * Cos);
    }
    bool operator < (const Point&that)const
    {
        return make_pair(x, y) < make_pair(that.x, that.y);
    }
    bool operator == (const Point &that ) const
    {
        return x == that.x && y == that.y;
    }
};

Point init[N], curr_point[N];
int link[N], multime[N];
bool vis[N];
map < Point , int > pos;
void Solve(int match_1)
{
    int difx = (init[match_1].x - curr_point[1].x), dify = (init[match_1].y - curr_point[1].y);
    for(int i = 1; i <= n; ++i)
    {
        link[i] = 0;
        vis[i] = false;
        multime[i] = 0;
    }

    for(int i = 1; i <= n; ++i)
    {
        Point need = Point(curr_point[i].x + difx, curr_point[i].y + dify);

        if(pos[need] != 0)
            link[i] = pos[need];
    }

    for(int i = 1; i <= n; ++i)
    {
        if(!vis[i] && link[i])
        {
            int j = i;
            vector < int > reach;

            while(j > 0 && !vis[j])
            {
                reach.push_back(j);
                vis[j] = 1;
                j = link[j];
            }

            if(reach.size() % 2)return;

            for(int i = 0; i + 1 < reach.size(); i += 2)
            {
                multime[reach[i]] = 1;
                multime[reach[i + 1]] = 2;
            }
        }
    }

    for(int i=1;i<=n;++i)if(!multime[i])return;

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

    exit(0);
}
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", &init[i].x, &init[i].y);
        pos[init[i]] = i;
    }

    for(int rotation = 0; rotation <= 3; ++rotation)
    {
        for(int i = 1; i <= n; ++i)
        {
            curr_point[i] = init[i].rotated(rotation * 90);

        }

        for(int match_1 = 2; match_1 <= n; ++match_1)
        {
            Solve(match_1);

        }
    }

    return 0;
}