2015年2月3日 星期二

2015/02/03 2014-2015 ACM-ICPC, Central Europe Regional Contest (CERC 14), problem: (D) Wheels

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

int T;
int X[2000], Y[2000], R[2000];

vector<int> v[2000];
bool visit[2000];
queue<int> que;
int dir[2000];

ll p[2000], q[2000];

ll dis2(int a, int b)
{
    ll dx = X[a]-X[b];
    ll dy = Y[a]-Y[b];

    return dx*dx+dy*dy;
}

ll gcd(ll a, ll b)
{
    while( a && b )
    {
        if( a < b ) swap(a, b);
        a %= b;
    }

    return a+b;
}

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        int N;

        scanf("%d", &N);

        for(int Ni = 0; Ni < N; Ni++)
            scanf("%d %d %d", &X[Ni], &Y[Ni], &R[Ni]);

        for(int Ni = 0; Ni < N; Ni++)
            v[Ni].clear();

        for(int Ni = 0; Ni < N; Ni++)
            for(int Nj = 0; Nj < N; Nj++)
            {
                if( Ni == Nj ) continue;

                int r = R[Ni]+R[Nj];
                if( dis2(Ni, Nj) == r*r )
                    v[Ni].push_back(Nj);
            }

        fill(visit, visit+N, false);

        visit[0] = true;

        que.push(0);

        dir[0] = 0;
        p[0] = 1; q[0] = 1;

        while( !que.empty() )
        {
            int F = que.front();
            que.pop();

            for(int vi = 0; vi < v[F].size(); vi++)
                if( !visit[v[F][vi] ] )
                {
                    int t = v[F][vi];

                    visit[t] = true;
                    que.push(t);
                    dir[t] = 1-dir[F];

                    p[t] = p[F]*R[F];
                    q[t] = q[F]*R[t];

                    ll GCD = gcd(p[t], q[t]);
                    p[t] /= GCD;
                    q[t] /= GCD;
                }
        }

        for(int Ni = 0; Ni < N; Ni++)
        {
            if( !visit[Ni] )
            {
                puts("not moving");
            }
            else
            {
                printf("%I64d", p[Ni]);
                if( q[Ni] != 1 ) printf("/%I64d", q[Ni]);

                if( dir[Ni] ) puts(" counterclockwise");
                else puts(" clockwise");
            }
        }
    }
}

沒有留言:

張貼留言