Cod sursa(job #2006336)

Utilizator lflorin29Florin Laiu lflorin29 Data 29 iulie 2017 14:46:02
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 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], in[N];
map < Point, int > pos;

bool go(int 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 0;

    for(int k = 0; k + 1 < reach.size(); k += 2)
    {
        multime[reach[k]] = 1;
        multime[reach[k + 1]] = 2;
    }return 1;
}
void Solve(int match_1, bool ok)
{
    int difx, dify;

    if(!ok)
        difx = (init[match_1].x - curr_point[1].x), dify = (init[match_1].y - curr_point[1].y);
    else
    {
        difx = (curr_point[match_1].x - init[1].x), dify = curr_point[match_1].y - init[1].y;
    }

    for(int i = 1; i <= n; ++i)
    {
        link[i] = 0;
        vis[i] = false;
        multime[i] = 0;
        in[i] = 0;
    }

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

        if(itr != end(pos))
            link[i] = itr->second, in[itr->second] = 1;
    }

    int cnt = 0;

    for(int i = 1; i <= n; ++i)
    {
        if(!vis[i] && link[i] && !in[i])
        {
            if(!go(i)) return ;
        }
    }
for(int i=1;i<=n;++i)if(!vis[i]&&link[i])
{
  if(!go(i))return ;
}
    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, 0);
            Solve(match_1, 1);
        }
    }

    return 0;
}