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

Обсуждение задачи 1422. Светлячки

Jabarov_Roman I can't understand what's wrong with my solution... [2] // Задача 1422. Светлячки 2 авг 2007 00:00
but it gives WA 1:(
could somebody find error in my source code or just
offer some effective tests where my program fails

here is solution
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_SIZE 2005
struct point
{
    int x,
        y,
        z;
    point(){};
    point(int _x,int _y,int _z):x(_x),y(_y),z(_z){};
} mas[MAX_SIZE],tmp[MAX_SIZE];
bool operator==(point & a,point & b)
{
    return ((a.x==b.x)&&(a.y==b.y)&&(a.z==b.z));
}
int n;
int gcd(int a,int b)
{
    if (b==0)
        return a;
    else gcd(b,a%b);
}
void input()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&mas[i].x,&mas[i].y,&mas[i].z);
}
bool cmp(point & a,point & b)
{
    if (a.x<b.x)
        return true;
    else if (a.x==b.x)
        if (a.y<b.y)
            return true;
        else if (a.y==b.y)
            return (a.z<b.z);
    return false;
}
point GetPoint(int i,int j)
{
    point first = mas[i];
    point second = mas[j];
    first.x = second.x - first.x;
    first.y = second.y - first.y;
    first.z = second.z - first.z;
    int GCD = gcd(gcd(first.x,first.y),first.z);
    if (GCD!=0)
    {
        first.x /= GCD;
        first.y /= GCD;
        first.z /= GCD;
    }
    return first;
}

int Calc(int yk)
{
    if (!yk)
        return 0;
    int maxAmount = 0;
    int cur = 1;
    for(int i=1;i<yk;i++)
        if (tmp[i]==tmp[i-1])
            cur++;
        else
        {
            if (cur>maxAmount)
                maxAmount = cur;
            cur = 1;
        }
    if (cur>maxAmount)
        maxAmount = cur;
    return maxAmount;
}
void solve()
{
    point base;
    int maxAmount = -1;
    for(int i=0;i<n;i++)
    {
        int yk = 0;
        for(int j=0;j<n;j++)
            if (i!=j)
                tmp[yk++] = GetPoint(i,j);
        sort(tmp,tmp+yk,cmp);
        int cur = Calc(yk) + 1;
        if (cur>maxAmount)
            maxAmount = cur;
    }
    printf("%d",maxAmount);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
    input();
    solve();
    return 0;
}
Jabarov_Roman Re: I can't understand what's wrong with my solution... [1] // Задача 1422. Светлячки 3 авг 2007 06:27
now it's tle 18
i just substituted this lines
int gcd(int a,int b)
{
if (b==0)
return a;
else gcd(b,a%b);
}
to
int gcd(int a,int b)
{
if (b==0)
return a;
else return gcd(b,a%b);
}
AC now :)