Page 2 of 4

### 270 - Lining Up

Posted: Fri Jan 23, 2004 1:04 am
Hi,

After a few RE I realized that 700 is not the right limit. I set it to 2000 and I got RE again. Can somebody (who got AC) tell me what limit should I set?

yaro

Posted: Fri Jan 23, 2004 8:06 am
If you mean the limit for X and Y coordinates, then there is no limit... but you can safely use an integer (32 bit, signed).

Posted: Sun Jan 25, 2004 1:55 am
Yes I know that. But what is the limit for number of points (number of X,Y pairs)?

thx

Posted: Tue Jan 27, 2004 9:23 am
My accepted code says 700 is quite enough. May the problem be in the input part of your code? Posted: Tue Jan 27, 2004 6:07 pm
I tried many diffrent kinds of multiple input readings and nothing. Now I'm wondering about the type of coordinate, but I got upset with this task and now I'm doing something else.

Thanks

Posted: Wed Jan 28, 2004 4:53 am
yaro wrote:I tried many diffrent kinds of multiple input readings and nothing. Now I'm wondering about the type of coordinate, but I got upset with this task and now I'm doing something else.

Thanks
I believe this problem has multiple inputs.. so maybe you should look at that.

Posted: Wed Jan 28, 2004 2:43 pm
junbin wrote:I believe this problem has multiple inputs.. so maybe you should look at that.
There shouldn't be multiple input problems in Vol. II anymore:
http://online-judge.uva.es/board/viewtopic.php?t=4820

Ciao!!!

Claudio

Posted: Wed Jan 28, 2004 3:27 pm
Yes.. there are no multiple inputs, but the format of the input is similar to multiple inputs and in the problem statement, the sample data only has only 1 input.. I'm merely warning him to be careful of the extra blank line between inputs.

Posted: Wed Mar 10, 2004 3:13 am I've got several RE on this problem, can anyone give me
some hints ?
Thank you!

Posted: Wed May 26, 2004 9:54 pm

Posted: Mon Sep 20, 2004 4:12 am
Hi,

I tried to solve the 270 and for the test cases of Waterloo I receive AC but in UVA i got TLE.

Why? the read of data I think that is correct [cpp]
#include <stdio.h>
#include <stdlib.h>

#define MAX 2000

typedef struct {
int x, y;
} point;

int ccw(point p0, point p1, point p2) {
int dx1, dx2, dy1, dy2;

return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}

int max (int a, int b) {
if (a > b) return a;
return b;
}

int main() {

#ifndef ONLINE_JUDGE
freopen("270.in", "r", stdin);
//freopen("270.out", "w", stdout);
#endif

int i, j, k, x, y, inst;
int num_pontos;
char linha;
point pontos[MAX];

scanf("%d\n", &inst);

for (; inst > 0; inst--) {
/*scanf("%d", &num_pontos);
if (num_pontos == 0) break;

for (i = 0; i < num_pontos; i++) {
scanf("%d %d", &x, &y);*/
i = 0;
while (gets(linha) != NULL && sscanf(linha, "%d %d", &x, &y) == 2) {
//printf("%d %d\n", x, y);
pontos.x = x;
pontos[i++].y = y;
}
num_pontos = i;
y = 0;
for (i = 0; i < num_pontos; i++) {
for (j = i + 1; j < num_pontos; j++) {
if (i == j) continue;
x = 2;
for (k = 0; k < num_pontos; k++) {
if (k == i || k == j) continue;
if (ccw(pontos, pontos[j], pontos[k]) == 0) {
x++;
}
}
y = max(x, y);
}
}

printf("%d\n\n", y);
}

while(true);
return 0;
}
[/cpp]

Thanks!

I have other problem - 274. it in the same situation! Posted: Thu Sep 23, 2004 5:26 am
Ok!

I got AC.. but with other code.. I wrote the code in n^2 ... in n^3 not is possible got AC in this problem.

Wanderley

### 270 What's the Problem????

Posted: Mon Aug 21, 2006 11:38 pm
I got WA but why???

Here is my code:

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define pi (2*acos(0.0))

int sort_int(const void *a,const void *b)
{
return (*(int*)a-*(int*)b);
}
void main()
{
long x,y,test;
int T,i,j,count,max,first,flag = 0;
char in,*p;
double theta;
//freopen("270.in","r",stdin);
scanf("%ld",&test);
gets(in);
gets(in);
while(test--)
{

i = 0;
while(gets(in)!=NULL)
{
if(in=='\0')
break;
p = strtok(in," ");
x = atol(p);
p = strtok(NULL," ");
y = atol(p);

if(x<0.0000001)
T[i++] = 0.0;
else if(y<0.000001)
T[i++] = 90;
else
{
theta = atan((double) y/x);
theta*=180;
theta/=pi;
T[i++] = theta;
}

}
qsort(T,i,sizeof(T),sort_int);
max = 0;
first = T;
count = 0;
for(j = 0;j<i;j++)
{
if(first==T[j])
{
count++;
}
else
{
if(count>max)
max = count;
count = 1;
first = T[j];
}
}
if(flag==0)
printf("%d\n",max);
else
printf("\n%d\n",max);
flag = 1;
}

}``````
Any Problem in my Algorithm????

Posted: Mon Dec 10, 2007 12:58 am
Hi all:
In the past I got AC in this problem using different ways in n^2logn.
Today i found my self getting WA in all of my codes.
Any help/hints/tricky test cases?
Does administrators change the test cases for this problem?

### perhaps

Posted: Tue Dec 11, 2007 12:37 am
Hi 898989,
try this.
use the output:

Code: Select all

``````A\n\n
A\n\n
A\n``````
and don't:

Code: Select all

``````A\n\n
A\n\n
A\n\n    <---- \n  :o
``````
perhaps work. [/quote]