476 - Points in Figures: Rectangles

[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]

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]

I follow your suggestion and I got accepted.
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]

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]

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]

[junjieliang]

From what I know, the points are not necessarily in the order (upperleftx, upperlefty, bottomrightx, bottomrighty)

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

[Robbie]

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

Hope this will help ![/pascal]

[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'.

[Robbie]

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]

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.

[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]

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 

[kallal]

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

[the LA-Z-BOy]

why not?