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

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

Post by mf » Sun Apr 10, 2005 12:03 pm

You have problems with rounding. Using floating point in this problem is kind of lottery.

Here's a rounding function which does not make use of any floats.

Code: Select all

int round1(int p, int q)   /* Rounds fraction p/q */
{
	return (p / q) + (((2 * (p % q)) >= q) ? 1 : 0);
}

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 » Mon Apr 11, 2005 11:05 am

Thank...u very much Mf I have got Ac..... :P
Ha it is a very easy problem but I use more time to do it......Again thanks...[/img][/quote][/b]
I hate Wrong Answer!

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

10823 Run Time error

Post by Karthekeyan » Mon Jan 02, 2006 6:32 pm

Could someone point out why?

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
struct square
{
	int blx,bly,side;
	int red,green,blue;
};
struct circle
{
	int centerx,centery,radius;
	int red,green,blue;
};
struct possibs
{
	int red,green,blue;
};
main()
{
	int tests;
	cin>>tests;
	int cases=1;
	while(tests>=cases)
	{

		cout<<"Case "<<cases<<":\n";
		int r,p;
		cin>>r>>p;
		vector<circle> circ;
		vector<square> sqr;
		for(int i=0;i<r;i++)
		{
			char str[7];
			cin>>str;
			if(strcmp(str,"CIRCLE")==0)
			{
				circle temp;
				cin>>temp.centerx>>temp.centery>>temp.radius;
				cin>>temp.red>>temp.green>>temp.blue;
				circ.push_back(temp);
			}
			else if(strcmp(str,"SQUARE")==0)
			{
				square temp;
				cin>>temp.blx>>temp.bly>>temp.side;
				cin>>temp.red>>temp.green>>temp.blue;
				sqr.push_back(temp);
			}
		}
		for(int i=0;i<p;i++)
		{
			int qx,qy;
			cin>>qx>>qy;
			int nc=circ.size();
			int ns=sqr.size();
			double red=0,green=0,blue=0;
			int count=0;
			for(int j=0;j<nc;j++)
			{
				int tempdt;
				tempdt=(qx-circ[j].centerx)*(qx-circ[j].centerx)+(qy-circ[j].centery)*(qy-circ[j].centery);
				if(tempdt<circ[j].radius*circ[j].radius)
				{
					red+=circ[j].red;
					green+=circ[j].green;
					blue+=circ[j].blue;
					count++;
				}
				else if(tempdt==circ[j].radius*circ[j].radius)
				{
					count++;
				}
			}
			for(int j=0;j<ns;j++)
			{
				if((qx>sqr[j].blx && qx<sqr[j].blx+sqr[j].side)&&(qy>sqr[j].bly && qy<sqr[j].bly+sqr[j].side))
				{
					red+=sqr[j].red;
					green+=sqr[j].green;
					blue+=sqr[j].blue;
				
					count++;
				}
				else if((qx==sqr[j].blx)&&(qy>=sqr[j].bly && qy<=sqr[j].bly+sqr[j].side))
				{
					count++;

				}
				else if((qx==sqr[j].blx+sqr[j].side)&&(qy>=sqr[j].bly && qy<=sqr[j].bly+sqr[j].side))
				{
					count++;

				}
				else if((qx>=sqr[j].blx && qx<=sqr[j].blx+sqr[j].side)&&(qy==sqr[j].bly))
				{
					count++;
				}
				else if((qx>=sqr[j].blx && qx<=sqr[j].blx+sqr[j].side)&&(qy==sqr[j].bly+sqr[j].side))
				{
					count++;
				}
			}
			int valred,valgreen,valblue;
			if((red/count-(int)(red/count)>0) && (red/count-(int)(red/count)<0.5))
				valred=(int)red/count;
			else if((red/count-(int)(red/count)>=0.5) && (red/count-(int)(red/count)<1))
				valred=(int)red/count+1;
			else
				valred=(int)red/count;

			if((green/count-(int)(green/count)>0) && (green/count-(int)(green/count)<0.5))
				valgreen=(int)green/count;
			else if((green/count-(int)(green/count)>=0.5) && (green/count-(int)(green/count)<1))
				valgreen=(int)green/count+1;
			else
				valgreen=(int)green/count;

			if((blue/count-(int)(blue/count)>0) && (blue/count-(int)(blue/count)<0.5))
				valblue=(int)blue/count;
			else if((blue/count-(int)(blue/count)>=0.5) && (blue/count-(int)(blue/count)<1))
				valblue=(int)blue/count+1;
			else valblue=(int)blue/count;

			cout<<"("<<valred<<","<<valgreen<<","<<valblue<<")\n";
		}
		cout<<'\n';
		cases++;
	}
}
Karthe

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10823 Run Time error

Post by Martin Macko » Sun May 21, 2006 1:40 am

Karthekeyan wrote:Could someone point out why?
Try the following input:

Code: Select all

1
0 1
4 7

filipius
New poster
Posts: 2
Joined: Thu Sep 28, 2006 11:07 am

When does round() fail

Post by filipius » Wed Nov 01, 2006 5:26 pm

mf wrote:You have problems with rounding. Using floating point in this problem is kind of lottery.

Here's a rounding function which does not make use of any floats.

Code: Select all

int round1(int p, int q)   /* Rounds fraction p/q */
{
	return (p / q) + (((2 * (p % q)) >= q) ? 1 : 0);
}
Hi,

first I had something like:

(int) Math.round(1.0 * p / q)

and I got wrong answer. When I changed the rounding procedure to the code posted above in function round1() the answer was immediately accepted.
I would be thankful if someone has a particular case where the division of two integers p and q leads to an incorrect result with the Math.round() function.

Thank you and regards,

Filipe Araujo
Portugal.

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

10823 - Of Circles and Squares

Post by mgavin2 » Sat Jul 28, 2012 6:36 pm

WA. I don't know. I've tried searching the discussions, I've tried fixing rounding errors, I've tried the sample input provided by other people and pass them all. But still get WA on submission. Can someone please debug my code?
TIA.

edit:
Got AC. I didn't compare the other outer edge of a square to the is_boun_square function.
all that matters is AC

Post Reply

Return to “Volume 108 (10800-10899)”