270 - Lining Up

[DP]

Code: Select all

cut

[helloneo]

I think sometimes ax can be 0..

[DP]

Nothing changed helloneo.
Still wrong answer.
I modified into this:

Code: Select all

if(ax>0.000001) tem=atan(ay/ax);
else tem=atan(0.0);

[helloneo]

Try this case..

Code: Select all

1

1 3
2 5
3 7
4 1

My output is..

Code: Select all

3

Hope this help..

[DP]

Thnx, silly mistake.

[forcebrute]

Before reading the posts I was trying this problem considering it multiple input one.
But after reading http://online-judge.uva.es/board/viewtopic.php?t=4820 I changed my solution.However , I am always getting Runtime Error. This is the code I am using

Code: Select all

#include<stdio.h>
#include<ctype.h>
int main()
	{
	
		int count=0,c=' ',flag='\0';
		int lmax,gmax=2;
		struct point {int x,y;};
		struct point p[700];
		while(	scanf("%d%d",&p[count].x,&p[count].y)==2){count++;}
		int i,j,k;
		for(i=0;i<count;i++)
		for(j=i+1;j<count;j++)
			{
			lmax=2;
			for(k=j+1;k<count;k++)
				if(p[i].x*p[j].y+p[j].x*p[k].y+p[k].x*p[i].y==p[i].y*p[j].x+p[j].y*p[k].x+p[k].y*p[i].x)
					lmax++;
			if(lmax>gmax)
				gmax=lmax;
			}
		printf("%d",gmax);
	return 0;
	}

I believe that the logic I am using is correct because I got AC on
http://acm.pku.edu.cn/JudgeOnline/problem?id=1118 using the following code which is same as above except that it handles several input cases

Code: Select all

#include<stdio.h>
#include<ctype.h>
int main()
       {
        while(1)
                {
                int count;
                int lmax,gmax=2;
                struct point {int x,y;};
                struct point p[1000];
                int i,j,k;
                scanf("%d",&count);
                if(count==0) break;
                for(i=0;i<count;i++)
                         scanf("%d%d",&p[i].x,&p[i].y);
                for(i=0;i<count;i++)
                for(j=i+1;j<count;j++)
                       {
                       lmax=2;
                       for(k=j+1;k<count;k++)
                               if(p[i].x*p[j].y+p[j].x*p[k].y+p[k].x*p[i].y==p[i].y*p[j].x+p[j].y*p[k].x+p[k].y*p[i].x)
                                        lmax++;
                       if(lmax>gmax)
                                 gmax=lmax;
                      }
                      printf("%d\n",gmax);
               }
            return 0;
          }

I would also like to ask why it is that the problem descriptions online on the site and that on pdf downloaded differ. The version online gives an impression that the problem is multiple input type but there is nothing in the pdf that says so.
Somebody help me please..

[mf]

It's a multiple input problem.

I would also like to ask why it is that the problem descriptions online on the site and that on pdf downloaded differ. The version online gives an impression that the problem is multiple input type but there is nothing in the pdf that says so.

In the old version of the judge, the problem statement (both html and pdf) specified format of a single case, and the fact that there were multiple cases was marked specially elsewhere, in a listing of problems of each volume. But now that's gone, and all html versions of such multiple-input problems were fixed, but not the .pdf's (because it's harder to do, I guess). So if ever see a difference between them, trust the html version.

[empo]

@Force brute
Why didnt you take input for number of test cases.....
i use this--->>>>>>>but getting Wrong Answer again again....Solve someone plzz.

Code: Select all

#include<iostream>
using namespace std;

struct pointy
{
    int x;
    int y;
}point[1000];

int main()
{
    int T,nop,i,j,k,max,count,flag=0;
	char str[10];
	  scanf("%d\n\n",&T);
      while(T--)
	{
        max = 0;
		nop=0;
		if(flag==1)
			cout<<endl;
		flag = 1;
		while (gets(str)!=NULL && str[0]!='\0')
		{
			sscanf(str,"%d %d",&point[nop].x,&point[nop].y);
			nop++;
		}
        for(i=0;i<nop;i++)
		{
            for(j=i+1;j<nop;j++)
			{
                count = 2;
                for(k=j+1;k<nop;k++)
				{
                    if((point[k].y-point[i].y)*(point[j].x-point[i].x)==(point[j].y-point[i].y)*(point[k].x-point[i].x))
                        count++;
				}
                if(count>max)
                    max = count;
			}
		}
        printf("%d\n",max);
	}
}

[forcebrute]

@empo
Read this http://online-judge.uva.es/board/viewtopic.php?t=4820

Is gets safe?? I don`t know.
But one possible reason you are getting a wrong answer is that output must be as follows
A\n\n
B\n\n
C\n\n

and not
A\n
B\n
C\n
as you have done

But even fixing this up and not using gets with the following code I am also getting wrong answer again and again. I have also changed every possible thing to long long just because of this.

Code: Select all

#include<stdio.h>
#include<ctype.h>
int main()
	{
	long long n,cases;
	scanf("%lld",&n);
	for(cases=0;cases<n;cases++)
		{
		long long count=0,c=' ',flag='\0';
		long long lmax,gmax=2;
		struct point {long long x,y;};
		struct point p[1000];
		do
			{
			ungetc(c,stdin);
			scanf("%lld%lld",&p[count].x,&p[count].y);
			scanf("%c",&c);
			flag=scanf("%c",&c);
			count++;
			}while(flag!=EOF && isdigit(c));
		long long i,j,k;
		for(i=0;i<count;i++)
		for(j=i+1;j<count;j++)
			{
			lmax=2;
			for(k=j+1;k<count;k++)
				if(p[i].x*p[j].y+p[j].x*p[k].y+p[k].x*p[i].y==p[i].y*p[j].x+p[j].y*p[k].x+p[k].y*p[i].x)
					lmax++;
			if(lmax>gmax)
				gmax=lmax;
			}
		printf("%lld\n\n",gmax);
		}
	return 0;
	}

[empo]

Now i am leaving this question as i think no one here has solved this question or get acepted..I checked a sample ouput in UVATOOLKIT too ...for input

Code: Select all

1

1 1
2 2
3 3
4 4
5 5
6 6
7 7
1 3

and Output we got in that is 8....how can it be possible???It should be 7....

[mf]

It seems to me that you're having troubles with parsing the input. Here's how I do it in my program:

Code: Select all

int x[1000], y[1000], n;
int solve() { /* solve a single case and return the answer */ }
int main() {
	char str[256];
	int t;
	for (scanf("%d", &t); t-- > 0;) {
		for (n = 0; gets(str);) {
			if (sscanf(str, "%d %d", &x[n], &y[n]) == 2) n++;
			else if (n != 0) break;
		}
		printf(t ? "%d\n\n" : "%d\n", solve());
	}
	return 0;
}

I checked a sample ouput in UVATOOLKIT too ...for input

Code: Select all

1

1 1
2 2
3 3
4 4
5 5
6 6
7 7
1 3

and Output we got in that is 8....how can it be possible???It should be 7....

Well, that means you've found a bug in uva toolkit, congrats.
What you should do now is report it to its author.

[empo]

@mf
I parshed my input very well....its giving right answers too..where the problem is lying is still hidden to me... i also tried your method and still giving wrong answer to me....

[mf]

Then the only thing I could think of is overflow in this line:

if((point[k].y-point.y)*(point[j].x-point.x)==(point[j].y-point.y)*(point[k].x-point.x))
count++;

Try to do this computation with a bigger data type than int.

[empo]

I try with long long but still giving me Wrong Answer/................

[shakil]

Why WA!!! Please help, give me some test case which my code fail. I Think my code is ok

Code: Select all

#include<stdio.h>
#include<string.h>

long x[709],y[709],cas,cas1,n,N,max;
long long X[709],Y[709],C[709],left[709],right[709]; 
long long t1,t2,p1,p2,i,j,root;
char temp[109];
int main()
{
    
gets(temp);
sscanf(temp,"%ld",&cas);
gets(temp);

for(cas1=1;cas1<=cas;cas1++)    
{    
n=0;
while(gets(temp))
{
if(sscanf(temp,"%ld %ld",&x[n],&y[n])==2)
n++;
else if(n!=0)
break;
}

max = 0;

if(n>0)
max=1;

for(i=0;i<n;i++)
{
N=0;
for(j=0;j<n;j++)  
if(i!=j)
{
t1=x[i]-x[j];
t2=y[i]-y[j];
if(N==0)
{
X[N]=t1;
Y[N]=t2;
C[N]=2;
left[N]=-1;
right[N]=-1;
N++;
if(max<2)
max=2;
}
else
{
root = 0;

while(1)
{
p1 = X[root] * t2;
p2 = t1 * Y[root];

if(p1==p2)
{
C[root]++;
if(C[root]>max)
max=C[root];
break;
}
else if(p1>p2)
{
if(left[root]!=-1)
root=left[root];
else
{
left[root]=N;
X[N]=t1;
Y[N]=t2;
C[N]=2;
left[N]=-1;
right[N]=-1;
N++;
break;
}
}
else
{
if(right[root]!=-1)
root=right[root];
else
{
right[root]=N;
X[N]=t1;
Y[N]=t2;
C[N]=2;
left[N]=-1;
right[N]=-1;
N++;
break;
}
}
}
    
}
}    
}    
printf("%ld\n",max);    
}    
return 0;    
}