## 476 - Points in Figures: Rectangles

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### ACM 476

This problem should be a very easy one. But I don't know why I can't
get "accepted". I think the code isn't wrong at all(at least I think
so). Can someone find out the bugs?
[c]
#include<stdio.h>
#define YES 1
#define NO 0
void main(void)
{
int x,n1,n2,found,y;
double a,b;
char c;
struct rectangle
{
double x1,x2,y1,y2;
}data;
for(x=0,n1=0;x<10;x++)
{
scanf("%s",c);
if(c=='*')
break;
scanf("%lf %lf %lf %lf",&data[x].x1,&data[x].y1,&data[x].x2,&data[x].y2);
n1++;
}
for(n2=1;;n2++)
{
scanf("%lf %lf",&a,&b);
if(a==9999.9 && b==9999.9)
break;
found=NO;
for(x=0;x<n1;x++)
if(a>data[x].x1 && a<data[x].x2 && b>data[x].y2 && b<data[x].y1)
{
printf("Point %d is contained in figure %d\n",n2,x+1);
found=YES;
}
if(!found)
printf("Point %d is not contained in any figure\n",n2);
}
}
[/c]
The response of ACM is always "Output Limit Exceed", but I don't know where the bugs are.
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
I think it's the problem of buffer overflow, i.e. an array of not enough size.

Try to declare the array of rectangle larger, e.g. 10000 and it will be accepted.

P.S. Despite the number of rectange < 10 as in the problem description, I think it's rejudged, so the number of rectangle is larger.

Hope can help~  htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### Thanks

And very very thanks!! But I am confused that the description is so tricky that I don't know if I should follow it. Maybe I will ignore them Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:

### 476/477/478 WA

Okay... I originally tried 477, cause it's my lucky #. I thought I had that right, but I kept on getting WA. Then I figured I'd try 476, thinking it might be a problem in the circle part of my program. Still got WA. Now, this seems like an easy problem. Is there something I'm missing? Any help would be great.

[java]
import java.io.*;
import java.util.*;

class Main{

static int pointNumber = 0;

byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try{
while (lg < maxLg){
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}catch (IOException e){ return (null); }
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main( String[] args ){
double[][] shapes = new double;
String temp = "";
int numShapes = -1;
while( (temp = ReadLn(250) ) != null ){
if( temp.indexOf( "*" ) != -1 ) break;
StringTokenizer tok = new StringTokenizer( temp );
numShapes++;
shapes[numShapes] = ( tok.nextToken().equals("r") ) ? 1.0 : 0.0;
shapes[numShapes] = parseDouble( tok.nextToken() );
shapes[numShapes] = parseDouble( tok.nextToken() );
shapes[numShapes] = parseDouble( tok.nextToken() );
shapes[numShapes] = parseDouble( tok.nextToken() );
}
boolean inside = false;
while( ( temp = ReadLn( 250 ) ) != null ){
pointNumber++;
StringTokenizer tok = new StringTokenizer( temp );
inside = false;
double x = parseDouble( tok.nextToken() );
double y = parseDouble( tok.nextToken() );
if( x == 9999.9 && y == 9999.9 ) break;
for( int i = 0; i <= numShapes; i++ )
if( contains( shapes, x, y, i ) ) inside = true;
if( !inside )
System.out.println("Point " + pointNumber + " is not contained in any figure" );
}
}

static boolean contains( double[] shape, double x, double y, int i ){
if( ( x > shape && x < shape ) && ( y > shape && y < shape ) ){
System.out.println( "Point " + pointNumber + " is contained in figure " + (i+1));
return true;
}
return false;
}

public static double parseDouble(String t)
{
int temp = t.indexOf('.');
if(temp == -1)
return Integer.parseInt(t);
String a = t.substring(0, temp);
int x = 0;
if(!a.equals("")) x = Integer.parseInt(a);
a = t.substring( temp + 1 );
int z = 0;
if( !a.equals("") ) z = Integer.parseInt(a);
temp = 1;
for(int i = 0; i < a.length(); i = i + 1)
temp = temp * 10;
x = temp * x + z;
return ((double) x )/ temp;
}
}
[/java]
emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

### 476 problem HELP!

Hi, I don't know what is wrong with my program, so that it always get WA?
Is there any special tricks or something like that?

[cpp]
#include <iostream.h>
#include <math.h>

typedef struct{
double x,y;
}tPoint;

class rectangle{
private:
tPoint upper,lower;

public:
int isInside(tPoint p){
if ( upper.x - p.x > 0 ) return 0;
if ( p.x - lower.x > 0 ) return 0;
if ( p.y - upper.y > 0 ) return 0;
if ( lower.y - p.y > 0 ) return 0;
return 1;
}

cin >> upper.x >> upper.y >> lower.x >> lower.y;
}
};

int main(void){
char c;
rectangle r;
int n=0;

cin >> c;
while (c != '*'){
cin >> c;
n++;
}

tPoint p;
cin >> p.x >> p.y;
int rc=0;
while (true){
int found = 0;

for (int i=0; i<n; i++){
if (r.isInside(p)){
cout << "Point " << rc+1 << " is contained in figure " << i+1 << endl;
found = 1;
}
}

if (!found)
cout << "Point " << rc+1 << " is not contained in any figure" << endl;

rc++;
cin >> p.x >> p.y;

if (fabs (p.x - 9999.9) < 0.00001 ) break;
if (fabs (p.y - 9999.9) < 0.00001 ) break;
}

return 0;
}
[/cpp]
-mk
junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

### Trick

From what I know, the points are not necessarily in the order (upperleftx, upperlefty, bottomrightx, bottomrighty)
emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:
This is what I quoted from the problem description:
The first character will designate the type of figure (``r'' for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.
I have updated my code, and make sure that:
upper.x < lower.x, and
upper.y > lower.y
cin >> upper.x >> upper.y >> lower.x >> lower.y;
int temp;
if (upper.x > lower.x){
temp = upper.x;
upper.x = lower.x;
lower.x = temp;
}

if (upper.y < lower.y){
temp = upper.y;
upper.y = lower.y;
lower.y = temp;
}
}[/cpp]
so, everything should be correct.
-mk
Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

### Re: 476 problem HELP!

May be you haven't considered when a point lie on one side of the rectangles.

Hope this will help ![/pascal]
emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:
I have changed the function rectangle.isInside() to be like the following function, to make
sure that if the point lies outside the boundary, then it will return 0

[cpp]int rectangle::isInside(tPoint p){
if ( upper.x - p.x > 0.00001 ) return 0;
if ( p.x - lower.x > 0.00001 ) return 0;
if ( p.y - upper.y > 0.00001 ) return 0;
if ( lower.y - p.y > 0.00001 ) return 0;
return 1;
}[/cpp]

but, I still not have it 'accepted'.
-mk
Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam
emka wrote:I have changed the function rectangle.isInside() to be like the following function, to make
sure that if the point lies outside the boundary, then it will return 0

[cpp]int rectangle::isInside(tPoint p){
if ( upper.x - p.x > 0.00001 ) return 0;
if ( p.x - lower.x > 0.00001 ) return 0;
if ( p.y - upper.y > 0.00001 ) return 0;
if ( lower.y - p.y > 0.00001 ) return 0;
return 1;
}[/cpp]

but, I still not have it 'accepted'.

I think you should change it in this way :

[cpp]int rectangle::isInside(tPoint p){
if ( upper.x - p.x >= 0) return 0;
if ( p.x - lower.x >= 0) return 0;
if ( p.y - upper.y >= 0) return 0;
if ( lower.y - p.y >= 0) return 0;
return 1;
}[/cpp]

Good luck emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:
WOW!!  I was surprised why it can get accepted...
So the main problem is that the point can lies on the edge of the rectangle, right...

thanks anyway.
-mk
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
while (!((x == 9999.9) && (y == 9999.9)))

it's dangerous to use == with floating point numbers.. my guess is this never ended and you just kept on doing the last case..
deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
perhaps reading the input by line and converted it into double
is safer than rather read it directly into double

this is some part of input reading from my solution, maybe it could
help

Code: Select all

``````while (gets (line)) {
last = 0;
sscanf (line,"%lf %lf",&x,&y);
if (x == 9999.9 && y == 9999.9) break;
for (i=0;i<pos_rec;i++)
{
process_rec (x,y,rec,i,&last);
}

if (!last) printf ("Point %d is not contained in any figure\n",set);
set ++;
}``````
and one more thing that looked weird too me in your solution

[/code]for(i = 0; i < 10; i++)
{
scanf("%s", temp);
if (temp == '*')
break;
scanf("%lf %lf %lf %lf", &rec.x1, &rec.y1, &rec.x2, &rec.y2);
}

Code: Select all

``````
I think it would be safer if you change the

for(i = 0; i < 10; i++)

into :

while (1)

GOOD LUCK  :P ``````
kallal
New poster
Posts: 4
Joined: Wed Jun 11, 2003 7:11 pm
Contact:

Can I use strtok() and atof() instead of sscanf() ? 