## 10823 - Of Circles and Squares

Moderator: Board moderators

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Code.

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

Code: Select all

``// Bernardo E. L``
_.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

### Re: Code.

_.B._ wrote: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)

borde = false;
return true;
else
borde = true; // Point lies on the edge.

return false;
}

``````
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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### :O

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?

_.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It may be the reason of WA.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### ACed :)

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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### [binary]10[/binary] questions.

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??

_.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: [binary]10[/binary] questions.

_.B._ wrote: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) .
_.B._ wrote: 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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### :eR

Greetings!
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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

### Re: [binary]10[/binary] questions.

mf wrote:
_.B._ wrote: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
_.B._ wrote: 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:

thanks I delete the code after i have got the Ac
Thanks every body
Last edited by J&Jewel on Mon Apr 11, 2005 11:10 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Re: [binary]10[/binary] questions.

sumankar wrote:Working with 16 bits will be fast on a 16 bit machine, 32 bits on a 32 bits...
mf wrote: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
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
HI a solve it by add this code and the result u gave is satisfy.
[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]