Page 3 of 4

Posted: Thu Feb 07, 2008 5:33 pm
by DP

Code: Select all

cut

Posted: Fri Feb 08, 2008 6:32 am
by helloneo
I think sometimes ax can be 0..

:-)

Posted: Fri Feb 08, 2008 12:20 pm
by 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);

Posted: Fri Feb 08, 2008 1:04 pm
by 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.. :-)

Posted: Fri Feb 08, 2008 2:11 pm
by DP
Thnx, silly mistake.

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

Posted: Wed Dec 03, 2008 7:48 pm
by 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..

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

Posted: Wed Dec 03, 2008 9:29 pm
by 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.

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

Posted: Thu Dec 04, 2008 7:57 am
by 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);
	}
}

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

Posted: Thu Dec 04, 2008 8:29 am
by 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;
	}

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

Posted: Thu Dec 04, 2008 5:02 pm
by 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....

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

Posted: Thu Dec 04, 2008 5:38 pm
by 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;
}
empo wrote: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.

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

Posted: Thu Dec 04, 2008 7:35 pm
by 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....

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

Posted: Thu Dec 04, 2008 7:44 pm
by 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.

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

Posted: Sat Dec 06, 2008 9:30 am
by empo
I try with long long but still giving me Wrong Answer/................

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

Posted: Thu Feb 25, 2010 7:08 pm
by 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;    
}