## 10823 - Of Circles and Squares

Moderator: Board moderators

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### 10823 - Of Circles and Squares

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### precision error..

watch out for precision error...

11 / 2 = 5.49999999999999 and not 5.50000000000000
So add necessary eps to handle this case.
marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
Or don't use floating point numbers at all. When computing a/b (a,b positive integers), you can use:

a/b - if rounding down
(a+b-1)/b - if rounding up
(2*a+b)/(2*b) - if rounding to the nearest integer (with 0.5 up)

Where / is the integer division.
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### Thank you very much!

I got it accepted. You were right.
sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
One small doubt:

Suppose a point lies on the boundary of a square which is overlapped by some other circle/square.What should the output color be?I assumed it would be black, but is it that we find the color using the same avg formula described in the problem?

Regards,
Suman.
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
...The problem...

The color of a point is computed as the average red, average green and average blue values of the geometric objects that this point falls into. If the point is on the borderline of any of the geometric object, then its color would be black; if it falls in the empty space, the color of the point would be white.

So you do not compute it using the average formula..., regards,

Yandry.
supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

### Re: precision error..

sohel wrote:watch out for precision error...

11 / 2 = 5.49999999999999 and not 5.50000000000000
So add necessary eps to handle this case.
I think this can be solved by:

Code: Select all

``````double ar = R / inCount + 0.5;
int iar = (int)ar;``````
When I participate the contest, this problem really confuses me....>"<
sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
The heart and soul of my program

Code: Select all

``````int onCircle(point p, point c, int len )
{
long r2 = len*len;
long d = (p.x-c.x)*(p.x-c.x) + (p.y-c.y)*(p.x-c.y);
if ( d == r2 )
return 0;
else if ( d < r2 )
return 1;
else return -1;
}
int onSquare(point p, point c, int len )
{
if ( p.x == c.x )
{
if ( (p.y >= c.y) && (p.y <= c.y + len) )
return 1;
}
if ( p.y == c.y )
{
if ( (p.x >= c.x) && (p.x <= c.x + len) )
return 1;
}
return 0;
}

int inSquare(point p, point c, int len)
{
return ( (p.x > c.x) && (p.x < c.x + len) &&
(p.y > c.y) && (p.y < c.y + len) ) ? 1 : 0;
}
``````
Can I get some i/o please ? I am tired with this.

Regards,
Suman.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Souldn't your function onSquare( (4,4) , (1,1), 3) return 1?
sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
Right on! You caught me napping.Thanks Little Joey.

Code: Select all

``````int onSquare(point p, point c, int len )
{
if ( p.x == c.x )
{
if ( (p.y >= c.y) && (p.y <= c.y + len) )
return 1;
}
if ( p.x == c.x + len )
{
if ( (p.y >= c.y) && (p.y <= c.y + len) )
return 1;
}
if ( p.y == c.y || (p.y == c.y+len) )
{
if ( (p.x >= c.x) && (p.x <= c.x + len) )
return 1;
}
if ( p.y == c.y + len )
{
if ( (p.x >= c.x) && (p.x <= c.x + len) )
return 1;
}
return 0;
}
``````
Trying to get it right the simplest way possible.Any more guesses ?
Regards,
Suman.[/code]
Last edited by sumankar on Sat Mar 12, 2005 2:20 pm, edited 1 time in total.
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Yeah, your function OnSquare is wrong, I am sure there is the mistake, try it checking the 4 sides of the square..., I mean:

bool side1, side2, side3, side4;

side1=...;
side2=...;
side3=...;
side4=...;

return side1 || side2 || side3 || side4;

sometimes partitioning makes things easier... , good luck,

Yandry.

Btw I was not accepted this ex within the 5 hours of the contest
sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
Even the function I posted now is wrong?
Did you check it?
Suman. sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Code: Select all

``````int tria(point a, point b, point c)
{
return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}

int onSquare(point p, point c, int len )
{
point d, e, f;
d.x = c.x; d.y = c.y + len;
f.x = c.x + len; f.y = c.y;
e.x = c.x + len; e.y = c.y + len;
return ( !tria(c, p, d) ||
!tria(d, p, e) ||
!tria(e, p, f) ||
!tria(f, p, c) );
}
``````
suman
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I think this will be fine:

int onSquare(point p, point c, int len )
{
if (c.x == p.x || c.x + len == p.x)
if (p.y >= c.y && p.y <= c.y + len)
return 1;

if (c.y == p.y || c.y + len == p.y)
if (p.x >= c.x && p.x <= c.x + len)
return 1;

return 0;
}

hope it helps... Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
why make it so complex... keep it simple... Code: Select all

``````
int onSquare(point p, point c, int len)
{
if(inSquare(p,c,len)) return 0;
return ( (p.x >= c.x) && (p.x <= c.x + len) &&
(p.y >= c.y) && (p.y <= c.y + len) ) ? 1 : 0;
}

``````