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

Post by yaro » 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?

Thanks in advance
yaro

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » 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).

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

Post by yaro » 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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » 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? :-?
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

Post by yaro » 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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » 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.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » 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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » 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.

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

Post by sunhong » Wed Mar 10, 2004 3:13 am

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

Post by Cosmin.ro » Wed May 26, 2004 9:54 pm


wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post by wanderley2k » 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 :roll:

[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

Post by wanderley2k » 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

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

270 What's the Problem????

Post by mohsincsedu » 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[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
Amra korbo joy akhdin............................

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » 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?

Thanks in advance.
Sleep enough after death, it is the time to work.
Mostafa Saad

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

perhaps

Post by adelar » 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]

Post Reply

Return to “Volume 2 (200-299)”