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

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

476 RTE!! PLZ HLP

Post by shihabrc »

THis code is generating RTE. I can't find why. can anyone hlp. plzz.

Code: Select all

#include<stdio.h>

typedef struct rectangle{
	char des[5];
	long double tlx,tly,brx,bry;
} rect;

typedef struct point{
	long double x,y;
} point;

void init(void);
void inits(void);
void swap(long double *,long double *);

rect r[1000];
point p[1000];
int flag[1000][1000];

void main(void){
	int i,j,q;
	char ch;
	while(1){
		scanf("%s",&r[0].des);
		if(r[0].des[0]=='*') break;
		scanf("%Lf %Lf %Lf %Lf",&r[0].tlx,&r[0].tly,&r[0].brx,&r[0].bry);
		if(r[0].tlx>r[0].brx) swap(&r[0].tlx,&r[0].brx);
		if (r[0].tly<r[0].bry) swap(&r[0].tly,&r[0].bry);
		ch=getchar();
		i=1;
		do{ 
			scanf("%s",&r[i].des);
			if(r[i].des[0]=='*') break;
			scanf("%Lf %Lf %Lf %Lf",&r[i].tlx,&r[i].tly,&r[i].brx,&r[i].bry);
			if(r[i].tlx>r[i].brx) swap(&r[i].tlx,&r[i].brx);
			if (r[i].tly<r[i].bry) swap(&r[i].tly,&r[i].bry);
			ch=getchar();
			i++;
		} while(r[i].des[0]!='*');
		i=0;
		init();
		do{
		    scanf("%Lf %Lf",&p[i].x, &p[i].y);
			if(p[i].x==9999.9 && p[i].y==9999.9) break;
			i++;
		} while(1);
		ch=getchar();
		if(!i) break;
		i=0;
		j=0;
		while(r[j].des[0]!='*'){
			i=0;
			while(p[i].x!=9999.9 && p[i].y!=9999.9){
				if(p[i].x>r[j].tlx && p[i].x<r[j].brx && p[i].y>r[j].bry && p[i].y<r[j].tly) flag[i][j]=1;
				i++;
			}
			j++;
		}
		q=-1;
		for(i=0;p[i].x!=9999.9 || p[i].y!=9999.9; i++){
			q=-1;
			for(j=0;r[j].des[0]!='*';j++){
				if (flag[i][j]) {
					printf("Point %d is contained in figure %d\n",i+1,j+1);
					q=1;
				}
			}
			if(q!=1) {
				printf("Point %d is not contained in any figure\n",i+1);
			}
		}
		inits();
	}
}


void init(void){
	int i,j;
	for(i=0;i<1000;i++){
		p[i].x=p[i].y=0;
		for(j=0;j<1000;j++){
			flag[i][j]=0;
		}
	}
}

void inits(void){
	int i;
	for(i=0;i<1000;i++){
		r[i].des[0]='0';
		r[i].brx=r[i].bry=r[i].tlx=r[i].tly=0;
	}
}

void swap(long double *a, long double*b){
	long double temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

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

Post by Jan »

I haven't found why you are getting RTE. May be checking code is boring enough. But I can give you some hint. You are using fl[1000][1000]. Why?

This problem is easy. You are given some rectangles with two co-ordinates - upper-left & lower-right. First store them. There are no more than 10 to store.

Suppose the co-ordinate of the upper-left corner is (x1,y1) and lower-right is (x2,y2). And the co-ordinate of the point is(x,y). Then the point is inside one of the rectangles x lies between x1 and x2 and y lies between y1 and y2.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

euleramon
New poster
Posts: 6
Joined: Sun Feb 27, 2005 7:02 am

476 Runtime Error

Post by euleramon »

I just tested my program and got correct answers on my PC. But I got a RE when submitting ? May anybody give me a hand ?
---
#include <stdlib.h>
#include <stdio.h>
class Rectangle
{
public:
int id;
float x1,y1,x2,y2;
/*Rectangle* m_next;
Rectangle* m_last;*/

Rectangle(int i)
{
id = i;
}
/*Rectangle* GetLast(void){ return(m_last); }
void SetLast(Rectangle *ptr){ m_last = ptr; }
Rectangle* GetNext(void){ return(m_next); }
void SetNext(Rectangle *ptr){ m_next = ptr; }*/

};
class Point
{
public:
int id;
float x,y;

Point(int i)
{
id = i;
}
};

bool theEnd(char* a)
{

if( a[0]=='9' && a[1]=='9' && a[2]=='9' && a[3]=='9' && a[4]=='.' && a[5]=='9'
&& a[6]==' ' && a[7]=='9' && a[8]=='9' && a[9]=='9' && a[10]=='9' && a[11]=='.' && a[12]=='9' && a[13]=='\0' )
return false;
else
return true;
}

int main()
{
char rString[40]="";
float r1x, r1y, r2x, r2y;
int i=0;
Rectangle* rectangle[10];

gets(rString);

for(i=0; rString[0] != '*'; i++)
{
sscanf( &(rString[0]), "r %f %f %f %f", &r1x, &r1y, &r2x, &r2y);
//printf("%f is float",r1x);
rectangle = new Rectangle(i);
rectangle->x1 = r1x;
rectangle->y1 = r1y;
rectangle->x2 = r2x;
rectangle->y2 = r2y;

//printf("%f is string\n",rectangle->x1);


gets(rString);
} // 有 i 個 rectangle



float px, py;
int notIn=0;
int j=0;
Point* point[400];

gets(rString);

for(j=0; theEnd(rString); j++)
{
sscanf( &(rString[0]), "%f %f", &px, &py);
point[j] = new Point(j);
point[j]->x = px;
point[j]->y = py;

gets(rString);
} // 有 j 個 point



for(int m=0; m<j; m++)
{
for(int k=0; k<i; k++)
{
if( rectangle[k]->x1 < point[m]->x && rectangle[k]->y1 > point[m]->y && rectangle[k]->x2 > point[m]->x && rectangle[k]->y2 < point[m]->y )
printf("Point %d is contained in figure %d\n",m+1,k+1);
else
{
notIn++;
if(notIn == i)
{
printf("Point %d is not contained in any figure\n",m+1);
notIn = 0;
}
}
}
notIn=0;
}

for(int k=0; k<i; k++)
{
delete rectangle[k];
}
for(int k=0; k<j; k++)
{
delete point[k];
}
return 0;
}
Before One Piece

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Are you sure that those last two are separated by a single space (or space at all)?

Please use code tags, it is easier to read. I didn't check past that part.

Darko

euleramon
New poster
Posts: 6
Joined: Sun Feb 27, 2005 7:02 am

Post by euleramon »

I amended my code into following. So it can skip any white space between numbers. But I still got Runtime Error. I wander if there are test samples to examine what's wrong with my program. Thank you.
---
#include <stdlib.h>
#include <stdio.h>
class Rectangle
{
public:
int id;
float x1,y1,x2,y2;
/*Rectangle* m_next;
Rectangle* m_last;*/

Rectangle(int i)
{
id = i;
}
/*Rectangle* GetLast(void){ return(m_last); }
void SetLast(Rectangle *ptr){ m_last = ptr; }
Rectangle* GetNext(void){ return(m_next); }
void SetNext(Rectangle *ptr){ m_next = ptr; }*/

};
class Point
{
public:
int id;
float x,y;

Point(int i)
{
id = i;
}
};

bool theEnd(char* a)
{

float p,q;
char b[20];
sscanf( &(a[0]),"%f %f", &p, &q);
//printf("%f %f",p ,q);

if( (p-9999.9)>0 && 1>(p-9999.9) && (q-9999.9)>0 && 1>(q-9999.9) )
return false;
else
return true;

}

int main()
{
char rString[40]="";
float r1x, r1y, r2x, r2y;
int i=0;
Rectangle* rectangle[10];

gets(rString);

for(i=0; rString[0] != '*'; i++)
{
sscanf( &(rString[0]), "r %f %f %f %f", &r1x, &r1y, &r2x, &r2y);
//printf("%f is float",r1x);
rectangle = new Rectangle(i);
rectangle->x1 = r1x;
rectangle->y1 = r1y;
rectangle->x2 = r2x;
rectangle->y2 = r2y;

//printf("%f is string\n",rectangle->x1);


gets(rString);
} // 有 i 個 rectangle



float px, py;
int notIn=0;
int j=0;
Point* point[400];

gets(rString);

for(j=0; theEnd(rString); j++)
{
sscanf( &(rString[0]), "%f %f", &px, &py);

point[j] = new Point(j);
point[j]->x = px;
point[j]->y = py;

gets(rString);
} // 有 j 個 point



for(int m=0; m<j; m++)
{
for(int k=0; k<i; k++)
{
if( rectangle[k]->x1 < point[m]->x && rectangle[k]->y1 > point[m]->y && rectangle[k]->x2 > point[m]->x && rectangle[k]->y2 < point[m]->y )
printf("Point %d is contained in figure %d\n",m+1,k+1);
else
{
notIn++;
if(notIn == i)
{
printf("Point %d is not contained in any figure\n",m+1);
notIn = 0;
}
}
}
notIn=0;
}

for(int k=0; k<i; k++)
{
delete rectangle[k];
}
for(int k=0; k<j; k++)
{
delete point[k];
}
return 0;
}
Before One Piece

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Why do you think there are at most 400 points? In general, if problem doesn't state bounds, assume the worst. but in this case 400000 did it. Remove the code after you get AC.

And, please use code tags (when you reply/edit you will see some buttons, one of them says "code" - press it, paste code, press it again, voila)

And(2) - I don't know much about C/C++, but I still don't like the way you are reading that last line in. Check the C/C++ forums for that.

Darko

euleramon
New poster
Posts: 6
Joined: Sun Feb 27, 2005 7:02 am

Post by euleramon »

I just followed your suggestion and got AC. You really give me a big hand. When I believed that the more outputs are correct which I tried, the more I am discouraged and couldn't find out where my wrong is. Fabulous!! You just got rid of my murkiness and inspired me to do in ACM again. I will conform your hint in "And(2)". Thank you very much .


---
Last edited by euleramon on Thu Mar 09, 2006 7:48 am, edited 1 time in total.
Before One Piece

euleramon
New poster
Posts: 6
Joined: Sun Feb 27, 2005 7:02 am

Post by euleramon »

Darko wrote:Why do you think there are at most 400 points? In general, if problem doesn't state bounds, assume the worst. but in this case 400000 did it. Remove the code after you get AC.

And, please use code tags (when you reply/edit you will see some buttons, one of them says "code" - press it, paste code, press it again, voila)

And(2) - I don't know much about C/C++, but I still don't like the way you are reading that last line in. Check the C/C++ forums for that.

Darko
Although I got AC, after that, I had modified my procedure "theEnd(char* a)" to achieve a really correct form. Thank you again.

Code: Select all

bool theEnd(char* a)
{
	char first[15];
	char second[15];
	char ending[]="9999.9";
	int flag=0;

	sscanf( &(a[0]),"%s  %s", first, second);

		for(int i=0; i<7; i++)
		{
			if( first[i]==ending[i] && second[i]==ending[i] )
				flag++;
		}	

		/*&& first[6]=='\0' && second[6]=='\0' && ending[6]==NULL*/ 
		if(	flag == 7 )
		{
			return false;
		}else
			return true;
	
}
Before One Piece

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

476, help me!

Post by deena sultana »

my dear friends, if u have some times, then plz see my code n i/o.
my prob is:
1. see my o/p, the last point is also checked. but i gave a break satement.
probably it's not working.

i dont know , hw can i eliminate this prob. :(

plz plz plz help me












emotionla_blind r u a magician?
u solved my prob again! THANK U SO MUCH. :lol:
Last edited by deena sultana on Mon Jun 19, 2006 7:06 pm, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

use

Code: Select all

if(fabs(x-9999.9)<0.1 && fabs(y-9999.9)<0.1)break;
for break


because float has some precesion problem.
if you give input 999.9 in x it may store 999.9000045 or like that so avoid this by given method hope it will help

keep posting

chiunyao
New poster
Posts: 4
Joined: Mon Feb 13, 2006 11:07 am

476 WA Please help me

Post by chiunyao »

Who can help me,i always get WA,but i don't know why??

please help me ..Thanks for all.

Code: Select all

#include<iostream>

using namespace std;

int main()
{
 	 char r;
 	 int i=0,count=0;
 	 int count2=0;
 	 float a,b,c,d; 
 	 float x[10][2]={0};
	 float 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; 
}

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali »

your output is

Code: Select all

Point 1 is contained in figure 2
Point 2 is contained in figure 2
Point 2 is contained in figure 3
Point 3 is contained in figure 3
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 6 is not contained in any figure
Point 7 is not contained in any figure
correct one is

Code: Select all

Point 1 is contained in figure 2
Point 2 is contained in figure 2
Point 2 is contained in figure 3
Point 3 is contained in figure 3
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 6 is not contained in any figure

chiunyao
New poster
Posts: 4
Joined: Mon Feb 13, 2006 11:07 am

Post by chiunyao »

Thanks for Artikali

but i key in these test data

ouput:

i don't know where is wrong?


Code: Select all

r 8.5 17.0 25.5 -8.5
r 0.0 10.3 5.5 0.0
r 2.5 12.5 12.5 2.5
*
2.0 2.0
Point 1 is contained in figure 2
4.7 5.3
Point 2 is contained in figure 2
Point 2 is contained in figure 3
6.9 11.2
Point 3 is contained in figure 3
20.0 20.0
Point 4 is not contained in any figure
17.6 3.2
Point 5 is contained in figure 1
-5.2 -7.8
Point 6 is not contained in any figure

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali »

Code: Select all

             x[i][1]=a; 
                      x[i][2]=c; 
                      y[i][1]=d; 
                      y[i][2]=b;
i think it would be like below

Code: Select all

                      x[i][0]=a; 
                      x[i][1]=c; 
                      y[i][0]=d; 
                      y[i][1]=b;
also change your test condition as above

pin0512
New poster
Posts: 2
Joined: Tue Jul 11, 2006 3:36 pm
Contact:

476 - Points in Figures: Rectangles

Post by pin0512 »

I still got WA , but I don't know why? :( Can anyone help me?Thanks!
This is my code:
#include<stdio.h>
float s[10][4];
int main()
{
char c;
int i,j=0,t=0,g=0,k=0;
double x,y;
while(1)
{
scanf(" %c",&c);
if(c=='*')break;
else
{
scanf(" %f %f %f %f",&s[t][0],&s[t][1],&s[t][2],&s[t][3]);
t++;
}
}
while(scanf("%lf %lf",&x,&y) !=EOF)
{
if(x==9999.9 && y==9999.9)break;
g++;
for(i=0;i<10;i++)
{
j++;
if((x>s[0] && x<s[2]) && (y<s[1] && y>s[3]))
{
k++;
printf("Point %d is contained in figure %d\n",g,j);
}
}
j=0;
if(k==0)printf("Point %d is not contained in any figure\n",g);
k=0;
}
return 0;
}

Post Reply

Return to “Volume 4 (400-499)”