ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1422. Fireflies

Show all messages Hide all messages

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;
}
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 :)