10823 - Of Circles and Squares

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Code.

Post by _.B._ » Tue Mar 15, 2005 5:20 am

Well, I'm tired of WAs again :evil:
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.

Post by sumankar » Tue Mar 15, 2005 5:55 am

_.B._ wrote:Well, I'm tired of WAs again :evil:
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.

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

:O

Post by _.B._ » Thu Mar 17, 2005 5:32 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Mar 17, 2005 7:11 am

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

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

ACed :)

Post by _.B._ » Fri Mar 18, 2005 5:50 am

Greetings!
Thanks a lot sumankar and Adrian!
I got some freaking error :o
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 :lol:
Finally!!
Going to look where it affected my program.

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

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

[binary]10[/binary] questions.

Post by _.B._ » Fri Mar 18, 2005 6:38 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by mf » Fri Mar 18, 2005 6:54 am

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

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

:eR

Post by _.B._ » Sat Mar 19, 2005 5:04 am

Greetings!
Thanks for the answer!
But still don't get it :wink:
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 8) , but working in my ASSEMBLER code :wink:

Keep posting!
_.

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

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

Post by sumankar » Sat Mar 19, 2005 9:16 am

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

Post by mf » Sat Mar 19, 2005 7:57 pm

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.

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

I got W/A i need some I/O...Please help!!!! here is my code.

Post by J&Jewel » Wed Mar 30, 2005 12:19 pm

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.
I hate Wrong Answer!

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

Post by mf » Wed Mar 30, 2005 6:06 pm

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)

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

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

Post by _.B._ » Thu Mar 31, 2005 4:10 am

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 8)

Keep posting!
_.

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Tue Apr 05, 2005 9:22 am

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]
I hate Wrong Answer!

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Sat Apr 09, 2005 8:37 am

Please
Give me some input/output.....pleaseeeeeeeeeee :D
I hate Wrong Answer!

Post Reply

Return to “Volume 108 (10800-10899)”