## 270 - Lining Up

Moderator: Board moderators

Ahshua
New poster
Posts: 7
Joined: Fri Jul 02, 2010 3:05 pm

### UVa 270,What's wrong with my programming???

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.

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
New poster
Posts: 3
Joined: Tue Jan 08, 2013 4:27 pm

### Re: 270: What's the limit for n???

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
New poster
Posts: 3
Joined: Tue Jan 08, 2013 4:27 pm

### Re: 270: What's the limit for n???

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
New poster
Posts: 1
Joined: Sun Dec 27, 2015 1:16 pm