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

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

### 270 - Lining Up

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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 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).

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland
Yes I know that. But what is the limit for number of points (number of X,Y pairs)?

thx

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
My accepted code says 700 is quite enough. May the problem be in the input part of your code?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland
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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 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.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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.

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

I've got several RE on this problem, can anyone give me
some hints ?
Thank you!

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm
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[256];
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!

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm
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

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

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

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[10000],i,j,count,max,first,flag = 0;
char in[100],*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]=='\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[0]),sort_int);
max = 0;
first = T[0];
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????

Amra korbo joy akhdin............................

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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?

Sleep enough after death, it is the time to work.

New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

### perhaps

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]