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

I can't understand what's wrong with my solution...
Posted by Jabarov_Roman 2 Aug 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;
}
Re: I can't understand what's wrong with my solution...
Posted by Jabarov_Roman 3 Aug 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);
}
Re: I can't understand what's wrong with my solution...
Posted by Jabarov_Roman 16 Nov 2007 02:23
AC now :)