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

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

ACM 476

Post by htl »

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[2];
struct rectangle
{
double x1,x2,y1,y2;
}data[10];
for(x=0,n1=0;x<10;x++)
{
scanf("%s",c);
if(c[0]=='*')
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:

Post by 10153EN »

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~ :D :D

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

Thanks

Post by htl »

I follow your suggestion and I got accepted.
And very very thanks!! :D
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

Post by Spike »

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;

static String ReadLn (int maxLg){
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try{
while (lg < maxLg){
car = System.in.read();
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[11][5];
String temp = "";
int numShapes = -1;
while( (temp = ReadLn(250) ) != null ){
if( temp.indexOf( "*" ) != -1 ) break;
StringTokenizer tok = new StringTokenizer( temp );
numShapes++;
shapes[numShapes][0] = ( tok.nextToken().equals("r") ) ? 1.0 : 0.0;
shapes[numShapes][1] = parseDouble( tok.nextToken() );
shapes[numShapes][2] = parseDouble( tok.nextToken() );
shapes[numShapes][3] = parseDouble( tok.nextToken() );
shapes[numShapes][4] = 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[1] && x < shape[3] ) && ( y > shape[4] && y < shape[2] ) ){
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!

Post by emka »

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?
anyone please help!

[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;
}

void readPoints(){
cin >> upper.x >> upper.y >> lower.x >> lower.y;
}
};

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

cin >> c;
while (c != '*'){
r[n].readPoints();
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

Post by junjieliang »

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:

Post by emka »

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
[cpp] void rectangle::readPoints(){
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!

Post by Robbie »

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:

Post by emka »

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

Post by Robbie »

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

emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

Post by emka »

WOW!! :o :o

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:

Post by Larry »

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

Post by deddy one »

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[0] == '*')
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 

User avatar
kallal
New poster
Posts: 4
Joined: Wed Jun 11, 2003 7:11 pm
Location: Bangladesh
Contact:

About 476

Post by kallal »

Can I use strtok() and atof() instead of sscanf() ? :cry:
Hi to all from Kallal !

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

why not?
Istiaque Ahmed [the LA-Z-BOy]

Post Reply

Return to “Volume 4 (400-499)”