## 476 - Points in Figures: Rectangles

Moderator: Board moderators

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

### Same problem I have??.

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
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!.

Thanks WR! I didn't consider the borders in any of them and all were AC 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 .
Ah!, and I had to use 1.0E30 for "pendientes" (slove?, slope?, don't remember ) 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

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;
int i,j,x;
int temp;
double ulx,uly,lrx,lry; /*Upper left x-y and lower right x-y*/
double pointx,pointy;
i=x=1;
for (i=1;i<=10;i++){
scanf("%c",&c);
if (c=='r'){
scanf("%lf %lf %lf %lf\n",&ulx,&uly,&lrx,&lry);
continue;
}
else if (c=='*'){
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
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:
thank you so much.
I change the code for this:
[c]
#include <stdio.h>

int main()
{
char c;
int i,j,x;
int temp;
double EPS = 0.0000001;
double ulx,uly,lrx,lry; /*Upper left x-y and lower right x-y*/
double pointx,pointy;
i=x=1;
for (i=1;i<=10;i++){
scanf("%c",&c);
if (c=='r'){
scanf("%lf %lf %lf %lf\n",&ulx,&uly,&lrx,&lry);
continue;
}
else if (c=='*'){
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! what other reason could it be??

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
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!

Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am
Hello!

You may fine it weird but try to do:

char st;
scanf ("%s", st);
if (st == '*') break;

Hope that may help; cheers!

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
Hi guys!!Thanks a lot for your help!!!!!!!   so sorry for my latency... Well...now I have retake the problems...and I still got WA in 476!!! here is my code:
[c]
#include <stdio.h>
#include <stdlib.h>

int main()
{
char str;
int i,j,x;
int temp;
double EPS = 0.0000001;
double temporal;
double ulx,uly,lrx,lry; /*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=='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=='*'){
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]

byeee!!!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
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

Code: Select all

``````#include <stdio.h>

int main(int argc, char **argv)
{
float a;
float b;
float c;
float d;
float x;
float y;
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
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
My signature:
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

code:
#include<iostream>

using namespace std;

int main(){
char r;
int i=0,count=0;
double a,b,c,d;
double x={0};
double y={0};
while(cin>>r){
if(r=='*') break;
else{
cin>>a>>b>>c>>d;
x[i]=a;
x[i]=c;
y[i]=d;
y[i]=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]<a&&x[j]>a&&y[j]<b&&y[j]>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
Contact:
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