## 270 - Lining Up

Moderator: Board moderators

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

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
I think sometimes ax can be 0..

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
Nothing changed helloneo.
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
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
Contact:
Thnx, silly mistake.

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

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

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.
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???

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???

@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???

@empo

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???

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???

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???

@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???

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???

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
Contact:

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

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