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

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

Why WA#54????
Послано <-UnderFelixAbove-> 4 сен 2007 00:21
Hi,Gues!

Please Help me! I have WA#54 and I don't understand what's wrong.

This is my code

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

struct sphere
{
    int x;
    int y;
    int z;
    int r;
    int num;
    bool met;
    sphere(){}
    sphere(int X,int Y,int Z,int R,int Num)
    {
        x = X;
        y = Y;
        z = Z;
        r = R;
        num = Num;
        met = false;

    }
} mas[1005];
int x,y,z,r;
int n;
string STR[1005];
int countSTR;
void input()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>x>>y>>z>>r;
        mas[i] = sphere(x,y,z,r,i);
    }
}
int posR;
int posW;
sphere Q[1005];
void Add(sphere sp)
{
    Q[posW++] = sp;
}
void zero()
{
    posR = 0;
    posW = 0;
    memset(Q,0,sizeof(Q));
}

bool isInter(sphere &a,sphere &b)
{
    int len = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z);
    int R = (a.r + b.r)*(a.r + b.r);
    if (len>=R)
        return false;
    return true;
}
void search(sphere sp)
{
    zero();
    sp.met = true;
    Add(sp);



    while(posR<posW)
    {
        sphere cur = Q[posR++];
        for (int i=0;i<n;i++)
        {
            if (mas[i].met == false)
                if (isInter(cur,mas[i]))
                {
                    mas[i].met = true;
                    Add(mas[i]);
                }
        }

    }
    int INT[1005];
    int countINT = 0;
    memset(INT,0,sizeof(INT));
    for (int i=0;i<posW;i++)
    {
        INT[countINT++] = Q[i].num;
    }
    sort(INT,INT+countINT);
    string str = "";
    char tmp[10];
    sprintf(tmp,"%i",INT[0]);
    str += tmp;
    for (int i=1;i<countINT;i++)
    {
        sprintf(tmp,"%i",INT[i]);
        str += ", ";
        str += tmp;
    }
    STR[countSTR++] = str;



}
void solve()
{
    for (int i=0;i<n;i++)
    {
        if (mas[i].met==false)
        {
            mas[i].met = true;
            search(mas[i]);
        }
    }
    sort(STR,STR + countSTR);
    for (int i=0;i<countSTR;i++)
    {
        cout<<STR[i]<<endl;
    }
}
int main()
{
    input();
    solve();
    return 0;
}