10823 - Of Circles and Squares

[_.B._]

Well, I'm tired of WAs again
Any help?

Code: Select all

// Bernardo E. L

[sumankar]

Well, I'm tired of WAs again
Any help?

Code: Select all

...
[snip]
/* How do you know, when this function returns true, that the point lies on the circle and not inside it? */
bool in_circle(objects objeto, bool &borde, sint x1, sint y1)
{ double aux_distancia = hipotenusa_al_cuadrado(objeto.x, objeto.y, x1, y1),
         radio_al_cuadrado = objeto.length * objeto.length;

  borde = false;
  if(aux_distancia < radio_al_cuadrado)
    return true;
  else
    if(aux_distancia == radio_al_cuadrado)
      borde = true; // Point lies on the edge.

  return false;
}

Thanks in advance!

Go back to the past few posts, you will find a lot said about inSquare/onSquare and inCircle/onCircle methods.Actually I used them as follows:

Code: Select all

 
+ inCircle() checks if the point lies completely in the circle or not
+ onCircle()  checks if the point lies on the circumference i.e circle's boundary or not.

On a similar note you can implement

Code: Select all

 
+ inSquare() 
+ onSquare() 

A cursory glance of your code revealed this much, maybe I'll give it a better shot after I've had my first cup of coffee
Regards,
Suman.

[_.B._]

Greetings!

How do you know, when this function returns true, that the point lies on the circle and not inside it?

Both functions return true if the point is inside a figure, and will make borde = true if the point is on the edge of a figure.

Any ideas why the WAs?

Thanks in advance!

[Adrian Kuegel]

Why are you using double for your function hipotenusa_al_cuadrado?
It may be the reason of WA.

[_.B._]

Greetings!
Thanks a lot sumankar and Adrian!
I got some freaking error
I changed the double to long long, and still got WA, but that gave me the idea to change:

Code: Select all

//typedef unsigned int usint;
typedef long usint;
//typedef int sint;
typedef long int sint;

And got it ACed
Finally!!
Going to look where it affected my program.

Keep posting!
And thanks again for your time and help!

[_.B._]

Now I have 2 questions:
1- Why is it that when I use unsigned int for longitud in my in_square function I get a WA?? (by using int I get it ACed).

Code: Select all

bool in_square(objects objeto, bool &borde, sint x, sint y)
{ unsigned int longitud = objeto.length;

  borde = false;
  if(x > objeto.x && x < (objeto.x + longitud) && y > objeto.y && y < (objeto.y + longitud))
    return true;
  else
  if((x == objeto.x || x == (objeto.x + longitud)) && y >= objeto.y && y <= (objeto.y + longitud))
    borde = true; // Point lies on one vertical side.
  else
  if(x >= objeto.x && x <= (objeto.x + longitud) && (y == objeto.y || y == (objeto.y + longitud)))
    borde = true; // Point lies on one horizontal side.

  return false;
}

2- Why is it that if I use short int instead of long int for my global variables it will solve the problem in twice the time??

Thanks in advance!

[mf]

Now I have 2 questions:
1- Why is it that when I use unsigned int for longitud in my in_square function I get a WA?? (by using int I get it ACed).

There are negative integers in the input. From the problem's statement: Each query point is denoted by an integer pair px and py (-1000 <= px,py <= +1000) .

2- Why is it that if I use short int instead of long int for my global variables it will solve the problem in twice the time??

"short" is a 16-bit integer type on the judge's system, while "int" and "long" are both 32-bit.

[_.B._]

Greetings!
Thanks for the answer!
But still don't get it
Don't know why the length must be negative.
And thought that working with 16 bits variables should be faster than working with 32 bits ones.
I guess my "Computer Architecture" classes are not that advanced yet , but working in my ASSEMBLER code

Keep posting!

[sumankar]

Now I have 2 questions:
1- Why is it that when I use unsigned int for longitud in my in_square function I get a WA?? (by using int I get it ACed).

There are negative integers in the input. From the problem's statement: Each query point is denoted by an integer pair px and py (-1000 <= px,py <= +1000) .

objeto.length is the radius of the circle/length of each side of a square which by the problem statement lies in [0, 2000].So that is not a correct observation.
The problem must be somewhere else

2- Why is it that if I use short int instead of long int for my global variables it will solve the problem in twice the time??

"short" is a 16-bit integer type on the judge's system, while "int" and "long" are both 32-bit.

Working with 16 bits will be fast on a 16 bit machine, 32 bits on a 32 bits
machine and so on.Speed really goes up when the data size is an integral
multiple of the native processor word size.So that for n words,
n fetches would be required(roughly, without going in to too much of a detail).

Now 16 bits short might suffer from the following problem -
C standard defines what values short can take , but not the internal implementation.So there may be padding bits, e.g. your short can be of 32 bits, where only the Least significant 16 bits are used, the rest are there for padding etc. So every time you use short the processor (having 32 bit native processor size, suppose) it has to fetch 32 bits only, strip the unwanted fat and get the results back to you!

Regards,
Suman.

[mf]

The problem is because the code mixes signed and unsigned integers. The standard says that "if either operand is unsigned int, the other is converted to unsigned int." (quote from K&R C 1988 edition, section A.6.5).

Here's a simple program:

Code: Select all

#include <stdio.h>

int main()
{
	int x;
	unsigned u;

	x = -2;
	u = 1;

	if ((x + u) > 0)
		printf("%d + %u: positive\n", x, u);
	else
		printf("%d + %u: non-negative\n", x, u);

	return 0;
}

I used GCC 3.3.1 (mingw), and the program above informed me that -2 + 1 is a positive integer.

The same kind of problem was in your code, _.B._.

What about the speed: I used only int and double in my program, and got 0.049 sec at the first submission, without any optimizations.

[J&Jewel]

thanks I delete the code after i have got the Ac
Thanks every body

[mf]

In your contain() function, when the object is a circle, you only test whether the point lies on the boundary. But you should also handle the case when the point is inside the circle.

Here are some test cases:

Code: Select all

1

2 3
CIRCLE 0 0 5   100 100 100
CIRCLE 0 0 5   100 150 100

0 0
0 5
4 3

And my output:

Code: Select all

Case 1:
(100, 125, 100)
(0, 0, 0)
(0, 0, 0)

[_.B._]

Working with 16 bits will be fast on a 16 bit machine, 32 bits on a 32 bits...

The problem is because the code mixes signed and unsigned integers. The standard says that "if either operand is unsigned int, the other is converted to unsigned int." (quote from K&R C 1988 edition, section A.6.5)...

Thanks a lot!, that's some really useful info

Keep posting!

[J&Jewel]

HI a solve it by add this code and the result u gave is satisfy.
but it still W/A . please help me to find the fault.
[else if(fig[k].type==2)
{
if((fig[k].x1-x)*(fig[k].x1-x) + (fig[k].y1-y)*(fig[k].y1-y) == (fig[k].r*fig[k].r))
return 3;
else if( (fig[k].x1-x)*(fig[k].x1-x) + (fig[k].y1-y)*(fig[k].y1-y) < (fig[k].r * fig[k].r))
return 2;
}][/code]

[J&Jewel]

Please
Give me some input/output.....pleaseeeeeeeeeee