ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1392. Тяга к звёздам

Help me! I have wa 1(((
Послано Denis 23 ноя 2007 00:04
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;

class sset
{
public:
    int p, rank;
};

sset a[1010];

void init (int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        a[i].p = i;
        a[i].rank = 0;
    }
}

int fset (int x)
{
    if (x != a[x].p)
    {
        a[x].p = fset (a[x].p);
    }
    return a[x].p;
}

void sset_union (int x, int y)
{
    if (a[x].rank < a[y].rank)
    {
        a[x].p = a[y].p;
    }
    else
    {
        a[y].p = a[x].p;
        if (a[x].rank == a[y].rank)
        {
            a[x].rank++;
        }
    }
}

int n;
string v[1010];
int c[1010][4] = {0};
int arr[1010] = {0};

bool is_in (int i, int j)
{
    int cd;
    cd = (c[i][0]-c[j][0])*(c[i][0]-c[j][0]) + (c[i][1]-c[j][1])*(c[i][1]-c[j][1]) + (c[i][2]-c[j][2])*(c[i][2]-c[j][2]);
    int rd = c[i][3]+c[j][3];
    rd *= rd;
    return rd > cd;
}

int main ()
{
    //freopen ("a.in", "r", stdin);
    //freopen ("a.out", "w", stdout);
    int i, j;
    int di;
    int p, q;
    scanf ("%d", &n);
    init (n);
    for (i = 0; i < n; ++i)
    {
        scanf ("%d%d%d%d", &c[i][0], &c[i][1], &c[i][2], &c[i][3]);
        di = -1;
        for (j = i-1; j >= 0; --j)
        {
            if (is_in(i, j))
            {
                p = fset (i);
                q = fset (j);
                sset_union (p, q);
            }
        }
    }
    for (i = 0; i < n; ++i)
    {
        j = fset(i);
        if (v[j] == "")
        {
            v[j] = (char)(i+'0');
        }
        else
        {
            v[j] += ", ";
            v[j] += (char)(i+'0');
        }
    }
    sort (v, v+n);
    for (i = 0; i < n; ++i)
    {
        if (v[i] != "")
        {
            cout<<v[i]<<endl;
        }
    }
    return 0;
}