Page 1 of 6

ACM 476

Posted: Sat Jun 29, 2002 6:13 am
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.

Posted: Sat Jun 29, 2002 7:45 am
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

Thanks

Posted: Sat Jun 29, 2002 12:50 pm
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 :(

476/477/478 WA

Posted: Wed Aug 28, 2002 12:16 am
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]

476 problem HELP!

Posted: Sat Oct 19, 2002 7:26 am
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]

Trick

Posted: Sat Oct 19, 2002 5:07 pm
by junjieliang
From what I know, the points are not necessarily in the order (upperleftx, upperlefty, bottomrightx, bottomrighty)

Posted: Sun Oct 20, 2002 1:30 am
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.

Re: 476 problem HELP!

Posted: Sun Oct 20, 2002 6:06 am
by Robbie
May be you haven't considered when a point lie on one side of the rectangles.

Hope this will help ![/pascal]

Posted: Sun Oct 20, 2002 9:47 am
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'.

Posted: Mon Oct 21, 2002 3:06 pm
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

Posted: Mon Oct 21, 2002 8:33 pm
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.

Posted: Fri Feb 14, 2003 6:58 pm
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..

Posted: Fri Feb 14, 2003 8:44 pm
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 

About 476

Posted: Fri Jun 13, 2003 8:30 pm
by kallal
Can I use strtok() and atof() instead of sscanf() ? :cry:

Posted: Tue Jun 17, 2003 1:45 pm
by the LA-Z-BOy
why not?