476 - Points in Figures: Rectangles

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Same problem I have??.

Post by _.B._ »

Greetings Eduard!.
Are you compiling in Free Pascal?.
If you do that, you'll see that if X:=9999.9, X = 9999.9 is FALSE!!.
Try this in Free Pascal:
[pascal]var
X:real;
begin
X:=9999.9;
writeLn (X-9999.9)
end.[/pascal]
I still don't know why, and I'm working on it right now.
If anyone programming in Pascal knows why, don't hesitate in posting it here :)

Thanks in advance for any responses.
_.B._
http://online-judge.uva.es/cgi-bin/Onli ... Info:42085

Code: Select all

P.S.: If the point is IN one of the sides, or if it IS one of the corners of the Rectangle, should it be considered as INSIDE the rectangle?.
Problem 477 specifies that points in borders are not considered inside, but this one doesn't specifies that.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

re 1:

Using Turbo Pascal 6.0 your program returned

Code: Select all

5.96046412226769E-0009 (real)
-3.64153152077051E-0013 (double)
 0.00000000000000E+0000 (extended)
so it's obviously a precision problem, but why ...? (don't know)

In my program (AC) I used

Code: Select all

if (Abs(xp-9999.9) < EPS) and (Abs(yp-9999.9) < EPS ) then ...
with

Code: Select all

const EPS: double = 0.0000001;
re 2:
P.S.: If the point is IN one of the sides, or if it IS one of the corners of the Rectangle, should it be considered as INSIDE the rectangle?.
Problem 477 specifies that points in borders are not considered inside, but this one doesn't specifies that.
I used the same routine in 476, 477 and 478 and all were accepted so
you shouldn't worry to much about that boundary problem.

bye

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Good!.

Post by _.B._ »

Thanks WR! :wink:
I didn't consider the borders in any of them and all were AC :D
And I believe it's precision problem, like you said.
I used (abs (X-9999.9) < 9E-12) and (abs (Y-9999.9) < 9E-12) and it worked alright too 8).
Ah!, and I had to use 1.0E30 for "pendientes" (slove?, slope?, don't remember :o ) when a line was paralel to the Y axis (X2-X1=0)

writeLn ('Later!');

_.B._

P.S.: I've got PLENTY of WAs by using only Turbo Pascal. Always try to compile and test using Free Pascal, like the Online-Judge does.

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

WA in 476

Post by midra »

I got stuck with this problem....it seems to be easy but I don't know WHY I GOT WA!
I made a simple code in C

[c]
#include <stdio.h>

int main()
{
char c[5];
int i,j,x;
int temp;
double ulx[12],uly[12],lrx[12],lry[12]; /*Upper left x-y and lower right x-y*/
double pointx,pointy;
i=x=1;
for (i=1;i<=10;i++){
scanf("%c",&c[0]);
if (c[0]=='r'){
scanf("%lf %lf %lf %lf\n",&ulx,&uly,&lrx,&lry);
continue;
}
else if (c[0]=='*'){
while(1){
scanf("%lf %lf",&pointx,&pointy);
if ((pointx==9999.9 && pointy==9999.9))
return 0;
temp=x;
for (j=1;j<=i;j++){
if (pointx>ulx[j] && pointx<lrx[j] && pointy<uly[j] && pointy>lry[j]){
printf("Point %d is contained in figure %d\n",x,j);
temp++;
}
if (x==temp && j>=i){
printf("Point %d is not contained in any figure\n",x);
break;
}
}
x++;
}
}
}
}
[/c]

It works fine for the sample Input/Output...
Is there any trick for this problem???
If someone can help I'm gonna appreciate very much!!
bye!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Hello midra,
if ((pointx==9999.9 && pointy==9999.9))
return 0;
probably is no good idea.

Did you try something like

Code: Select all

double EPS = 0.0000001;
...
if (abs(xp-9999.9) < EPS) && (abs(yp-9999.9) < EPS ) 
      return 0;
?

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra »

thank you so much.
I change the code for this:
[c]
#include <stdio.h>

int main()
{
char c[5];
int i,j,x;
int temp;
double EPS = 0.0000001;
double ulx[12],uly[12],lrx[12],lry[12]; /*Upper left x-y and lower right x-y*/
double pointx,pointy;
i=x=1;
for (i=1;i<=10;i++){
scanf("%c",&c[0]);
if (c[0]=='r'){
scanf("%lf %lf %lf %lf\n",&ulx,&uly,&lrx,&lry);
continue;
}
else if (c[0]=='*'){
while(1){
scanf("%lf %lf",&pointx,&pointy);
if ((abs(pointx-9999.9) < EPS) && (abs(pointy-9999.9) < EPS ) )
return 0;
temp=x;
for (j=1;j<=i;j++){
if (pointx>ulx[j] && pointx<lrx[j] && pointy<uly[j] && pointy>lry[j]){
printf("Point %d is contained in figure %d\n",x,j);
temp++;
}
if (x==temp && j>=i){
printf("Point %d is not contained in any figure\n",x);
break;
}
}
x++;
}
}
}
}[/c]

but still got WA! :cry:
what other reason could it be??

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Hi Midra,

I copied and tested your program and I didn't find any wrong answer yet (will keep trying). But for the sake of completeness: include stdlib for the abs-function and a return value.

And: are you sure you're mailing program doesn't gobble part of the file?
Happened before!

By the way, the problem statement says
... This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.
It doesn't say which comes first!

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo »

Hello!

You may fine it weird but try to do:

char st[5];
scanf ("%s", st);
if (st[0] == '*') break;

instead of scanf ("%c",...)

Hope that may help; cheers!

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra »

Hi guys!!Thanks a lot for your help!!!!!!! :D :D :D
so sorry for my latency... :oops:
Well...now I have retake the problems...and I still got WA in 476!!! :x

I have read your advices...and I make a little changes

here is my code:
[c]
#include <stdio.h>
#include <stdlib.h>

int main()
{
char str[5];
int i,j,x;
int temp;
double EPS = 0.0000001;
double temporal;
double ulx[12],uly[12],lrx[12],lry[12]; /*Upper left x-y and lower right x-y*/
double pointx,pointy;
i=x=1;
for (i=1;i<=10;i++){
scanf("%s",str);
if (str[0]=='r'){
scanf("%lf %lf %lf %lf\n",&ulx,&uly,&lrx,&lry);
if (ulx>lrx){
temporal=ulx;
ulx=lrx;
lrx=temporal;
}
if (uly[i]<lry[i]){
temporal=uly[i];
uly[i]=lry[i];
lry[i]=temporal;
}
continue;
}
else if (str[0]=='*'){
while(1){
scanf("%lf %lf",&pointx,&pointy);
if ((abs(pointx-9999.9) < EPS) && (abs(pointy-9999.9) < EPS ) )
return 0;
temp=x;
for (j=1;j<=i;j++){
if (pointx>ulx[j] && pointx<lrx[j] && pointy<uly[j] && pointy>lry[j]){
printf("Point %d is contained in figure %d\n",x,j);
temp++;
}
if (x==temp && j>=i){
printf("Point %d is not contained in any figure\n",x);
break;
}
}
x++;
}
}
}
}
[/c]

I have read all the posts in this forum about this problem and I can't understand why my code doesn't work!!!

well...if someone knows...advice me plz!!!
byeee!!!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Hi Midra,

did you test your program with exactly 10 rectangles?!

Vala
New poster
Posts: 3
Joined: Sun Jan 16, 2005 4:26 am

476 " Invalid memory reference" again .... and a

Post by Vala »

Code: Select all

#include <stdio.h>


int main(int argc, char **argv)
{
	float a[10];
	float b[10];
	float c[10];
	float d[10];
	float x[100];
	float y[100];
	int flag;
	int count1;
	int count2;
	int count3;
	int index;
	int exit;
	float input1,input2;
	char waste;
	
	count1=0;
	exit=0;
	
	while ((count1<=10)&&(exit==0))
	{
		scanf("r %f %f %f %f\n",&a[count1],&b[count1],&c[count1],&d[count1]) || (exit=1);
		count1++;
	}
	
	scanf("%c",&waste);
	
	count3=0;
	exit=0;
	
	while (((input1!=(float)9999.9)&&(input2!=(float)9999.9))&&(exit==0))
	{
		scanf("%f %f",&input1,&input2) || (exit=1);
		if ((input1!=(float)9999.9)&&(input2!=(float)9999.9))
		{
			x[count3]=input1;
			y[count3]=input2;
		}
		count3++;
	}
	
	index=0;
	
	while(index<=count3-2)
	{
		count2=0;
		flag=0;
		while (count2<=count1-2)
		{
			if ((x[index]>a[count2])&&(x[index]<c[count2])&&(y[index]<b[count2])&&(y[index]>d[count2]))
			{
				printf("Point %d is contained in figure %d\n",index+1,count2+1);
				flag=1;
			}
			count2++;
		}
		if (flag==0)
		{	printf("Point %d is not contained in any figure\n",index+1);	}
		index++;
	}
	
	return 0;
}
" Invalid memory reference"

Why's that ??

Vala
New poster
Posts: 3
Joined: Sun Jan 16, 2005 4:26 am

Post by Vala »

the program actually runs smoothly on my computer,
but .....

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

astralbeams
New poster
Posts: 4
Joined: Mon Jun 27, 2005 5:27 pm

476 WA

Post by astralbeams »

I can't find the bugs. Please help me!
code:
#include<iostream>

using namespace std;

int main(){
char r;
int i=0,count=0;
double a,b,c,d;
double x[10][2]={0};
double y[10][2]={0};
while(cin>>r){
if(r=='*') break;
else{
cin>>a>>b>>c>>d;
x[i][1]=a;
x[i][2]=c;
y[i][1]=d;
y[i][2]=b;
i++;
}
}
while(cin>>a>>b){
int count2=0;
if(a==9999.9&&b==9999.9) break;
else{
count++;
for(int j=0;j<i;j++){
if(x[j][1]<a&&x[j][2]>a&&y[j][1]<b&&y[j][2]>b){
cout<<"Point "<<count<<" is contained in figure "<<j+1<<endl;
count2=1;
}
}
}
if(count2==0) cout<<"Point "<<count<<" is not contained in any figure"<<endl;
}
return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Dont use double. Because it can make precision errors. Take the inputs as strings.

Code: Select all

/* suppose a[]=-8.2;
Then u can easily make it an integer.    */

l=strlen(a);
sum=0;
p=1;
for(i=0;i<l;i++)
{
    if(a[i]=='-')
        p=-1;
    else if(a[i]>='0'&&a[i]<='9')
        sum=sum*10+a[i]-48;
}
sum=sum*p;
/* So sum will be -82    */
Then the rest is like yours. :)
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 4 (400-499)”