270 - Lining Up

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Thu Feb 07, 2008 5:33 pm

Code: Select all

cut
Last edited by DP on Fri Feb 08, 2008 2:12 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Feb 08, 2008 6:32 am

I think sometimes ax can be 0..

:-)

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Fri Feb 08, 2008 12:20 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Feb 08, 2008 1:04 pm

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
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Fri Feb 08, 2008 2:11 pm

Thnx, silly mistake.

forcebrute
New poster
Posts: 4
Joined: Wed Dec 03, 2008 6:46 pm

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

Post by forcebrute » Wed Dec 03, 2008 7:48 pm

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..
Last edited by forcebrute on Thu Dec 04, 2008 8:31 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by mf » Wed Dec 03, 2008 9:29 pm

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
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

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

Post by empo » Thu Dec 04, 2008 7:57 am

@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);
	}
}
"Accepted" is my passion but RTE is my weakness.....

forcebrute
New poster
Posts: 4
Joined: Wed Dec 03, 2008 6:46 pm

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

Post by forcebrute » Thu Dec 04, 2008 8:29 am

@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
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

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

Post by empo » Thu Dec 04, 2008 5:02 pm

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....
"Accepted" is my passion but RTE is my weakness.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by mf » Thu Dec 04, 2008 5:38 pm

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.

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

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

Post by empo » Thu Dec 04, 2008 7:35 pm

@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....
"Accepted" is my passion but RTE is my weakness.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by mf » Thu Dec 04, 2008 7:44 pm

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
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

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

Post by empo » Sat Dec 06, 2008 9:30 am

I try with long long but still giving me Wrong Answer/................
"Accepted" is my passion but RTE is my weakness.....

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

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

Post by shakil » Thu Feb 25, 2010 7:08 pm

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;    
}
SHAKIL

Post Reply

Return to “Volume 2 (200-299)”