476 - Points in Figures: Rectangles
Moderator: Board moderators
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[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.
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.
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~

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~


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;
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]
[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!
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]
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
-
- 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)
This is what I quoted from the problem description:
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.
I have updated my code, and make sure that: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.
[cpp] void rectangle::readPoints(){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
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]
Hope this will help ![/pascal]
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'.
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
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

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
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);
}
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 ++;
}
[/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
-
- Learning poster
- Posts: 94
- Joined: Wed Jul 31, 2002 12:44 pm
- Location: Dacca, Bangladesh
- Contact: