270 - Lining Up

[Ahshua]

Help me,please!
I use the Two-point - form
(y-y1)/(y2-y1)=(x-x1)/(x2-x1) change into the Generation form Ax+By+C=0.I'm sure the derivation is correct.But I always got wrong answer !
Everyone give me a hand,I need help.
Thanks in advance!

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
typedef struct NODE
{
        int x,y;
};
NODE a[1024]={0};
int cas,n,maxs;
char s[64]={'\0'};
int main()
{
    int k,len,tmp,first,A,B,C;
    scanf("%d\n",&cas);
    for(int t=0;t<cas;t++)
    {
       n=0;
       maxs=1;
       while(gets(s)!=NULL)
       {
          if(!isdigit(s[0])) break;
          len=strlen(s);
          first=1; k=0;
          for(int i=0;i<=len;i++)
          if(isdigit(s[i]))
             k=k*10+s[i]-'0';
          else
          {
             if(first) a[n].x=k;
             else a[n].y=k;
             first=k=0;
          }
          n++;
       }
       for(int i=0;i<n-1;i++)
          for(int j=i+1;j<n;j++)
          {
             tmp=0;
             A=a[i].y-a[j].y;
             B=a[j].x-a[i].x;
             C=a[i].x*a[j].y-a[j].x*a[i].y;
             for(int k=0;k<n;k++)
                if(A*a[k].x+B*a[k].y+C==0)
                   tmp++;
             if(maxs<tmp) maxs=tmp;
          }
       if(t) printf("\n");
       printf("%d\n",maxs);
    }
    return 0;
}

[kien_coi_1997]

I got Wrong Answer.

Code: Select all

2

-6	-6
-8	-3
-2	-2
-6	-2
-2	0
-4	-4
-5	-1
-7	-8
-1	-1
-9	-8
-10	-6
-7	-4
-6	-4
-6	-9
-1	-9
-2	-10
-9	-6
-7	0
-2	-9
-7	-5
-9	-9
-10	-5

-9	-8
-10	-6
-7	-4
-6	-4
-6	-9
-1	-9
-2	-10
-9	-6
-7	0
-2	-9
-7	-5
-9	-9
-10	-5

My program output

Code: Select all

5

3

Is it right?

[kien_coi_1997]

Oh, I've found my mistake!!!

if you have a struct like that:

Code: Select all

#define long long long
struct line { long A, B, C; };

To minimize a line struct. I use this wrong algorithm.

Code: Select all

void minimize(line &d){
    long GCD = gcd(abs(A), abs(B), abc(C));
    if (d.A<0) GCD=-GCD;
    d.A/=GCD;
    d.B/=GCD;
    d.C/=GCD;
}

I've replace it by

Code: Select all

void minimize(line &d){
    long GCD = gcd(abs(A), abs(B), abc(C));
    if (d.A<0) GCD=-GCD;
    else if (d.A==0 && d.B<0) GCD=-GCD;
    else if (d.A==0 && d.B==0 && d.C<0) GCD=-GCD:
    d.A/=GCD;
    d.B/=GCD;
    d.C/=GCD;
}

and got AC
(but time is ...2.932)

[muneebawan]

Please help me. I am not clearly understanding the problem.
Do we have to check the sequence of the y co ordinate?
e.g if sequence is
x y
1 1
1 2
1 3
1 4
that means max points = 4.