270 - Lining Up

[yaro]

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?

Thanks in advance
yaro

[junbin]

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]

Yes I know that. But what is the limit for number of points (number of X,Y pairs)?

thx

[Observer]

My accepted code says 700 is quite enough. May the problem be in the input part of your code?

[yaro]

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]

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]

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]

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]

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

[Cosmin.ro]

http://oldsite.vislab.usyd.edu.au/educa ... node3.html

[wanderley2k]

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]

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]

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

Thanks in advance

[898989]

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?

Thanks in advance.

[adelar]

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]