10823 - Of Circles and Squares

[mf]

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);
}

[J&Jewel]

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

[Karthekeyan]

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++;
	}
}

[Martin Macko]

Could someone point out why?

Try the following input:

Code: Select all

1
0 1
4 7

[filipius]

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]

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?

Code: Select all

TIA.

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