375 - Inscribed Circles and Isosceles Triangles

[AlexandreN]

I think that there are errors with this problem.
For example, for the sample input I think that the sample output should be
0.827651 and not 0.827648 as stated in the problem.

This is my solution , I think it's correct but I'm getting wrong awnser.

-- code removed ---

I was doing a silly mistake, now got it accepted.

[Mahbub]

I think This problem requires a SPECIAL JUDGE. Because the sample output doesnt match exaclty with my output..although i used an analytic approach...

I used the follwing process..is it correct? Plz help:

.........
pi = acos(-1.0);
r = init.
while(r>=0.000001)
{
determine r;
sum = sum + r;
}

sum = 2 * pi * sum;

printf(sum);
...........

[SMBfromRU]

I've just got AC for this problem after 2 attempts.
Second (successful) variant had only 1 change: Single type to Double,
I wrote in Pascal.
Besides, in your variant I noticed one small bug:
you check r>=1.0e-6 BEFORE adding new calculated "r" to "sum". I think this last addition may cause wrong last digit in result.

One more thing, if it is good to compare "r" with immediate constant,
which is not clear type. More reliable, I think, to compare two identical typed variables, e.g. r>=r_min.

[little joey]

The number of WAs has long ago gone into double figures, and I don't get the rounding correct. This is absolutely stupid&frustrating. I'll publish one of my versions (not the most elegant):
[pascal]program p375;

var
b,h,r,rtot,rmin:double;
cases,caseno:integer;
begin
rmin:=0.000001;
read(cases);
for caseno:=1 to cases do begin
read(b,h);
if (caseno>1) then writeln;
rtot:=0.0;
repeat
r:=b*h/(2*(b+2*sqrt(sqr(h)+sqr(b)/4)));
rtot:=rtot+r;
if (r<=rmin) then break;
b:=b*(h-2*r)/h;
h:=h-2*r;
until false;
writeln((2*pi*rtot):13:6);
end;
end.[/pascal]
which I think _SHOULD_ be accepted.
Tried all sorts of calculation orders, types, etc. but nothing works.

It is one thing that the judge doesn't accept the analytical solution (pi*h, as can be verified by anyone with a 101 course in infinite series), but forces us to do the iterations (it's a programming contest after all). But IMHO it should show a little coulance with regard to the rounding errors. Getting the AC answer is purely a matter of chance...

Please judges, look into this matter and turn the blue flag into a green one. You would make this simple programmer very happy

Correct me if I'm wrong.

[eloha]

I got WA for this problem. I do not know what's wrong. Can anyone help me?
[c]
#include <stdio.h>
#include <math.h>

void main()
{
int testcase,i,t;
double B,H,b,ans,r,newH;
double pi=2.0*acos(0.0);

scanf("%d",&testcase);
for(t=1; t<=testcase; t++){
if(t!=1) printf("\n");
scanf("%lf %lf",&B,&H);
b=B/2.0;
ans=0.0;
while(1){
r=(sqrt(b*b*b*b+H*H*b*b)-b*b)/H;
if(r<0.000001) break;
ans += 2*pi*r;
newH = H-2.0*r;
b = b*newH/H;
H = newH;
}
printf("%13.6lf\n",ans);
}
}

[/c]

[supermin]

The following is my code.I got P.E.
If you got W.A.,you may check it with my code.

However,could anyone tell me about the standard I/O form.
Why I got P.E.

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double r,total;
	double H,B;
	int cases;
	double pi=2.0*acos(0.0);
	int nl=0;

	scanf("%d",&cases);

	while(cases-->0){		

		scanf("\n");
		scanf("%lf %lf",&B,&H);
		
		r=B/2*tan( 0.5 * atan( 2.0 * H / B ) );
		for(total=0;r>=0.000001;r=B/2*tan( 0.5 * atan( 2.0 * H / B ) )){
			total+=2*pi*r;
			H=H-2*r;
			B=( H/(H+2*r) ) * B ;
		}

		if(nl)
			putchar('\n');
		else 
			nl=1;
		printf("      %.6lf\n",total);	

	}

	return 0;
}

[supermin]

The following is my code.I got P.E.
If you got W.A.,you may check it with my code.

However,could anyone tell me about the standard I/O form.
Why I got P.E.

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double r,total;
	double H,B;
	int cases;
	double pi=2.0*acos(0.0);
	int nl=0;

	scanf("%d",&cases);

	while(cases-->0){		

		scanf("\n");
		scanf("%lf %lf",&B,&H);
		
		r=B/2*tan( 0.5 * atan( 2.0 * H / B ) );
		for(total=0;r>=0.000001;r=B/2*tan( 0.5 * atan( 2.0 * H / B ) )){
			total+=2*pi*r;
			H=H-2*r;
			B=( H/(H+2*r) ) * B ;
		}

		if(nl)
			putchar('\n');
		else 
			nl=1;
		printf("      %.6lf\n",total);	

	}

	return 0;
}

[supermin]

The following is my code.I got P.E.
If you got W.A.,you may check it with my code.

However,could anyone tell me about the standard I/O form.
Why I got P.E.

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double r,total;
	double H,B;
	int cases;
	double pi=2.0*acos(0.0);
	int nl=0;

	scanf("%d",&cases);

	while(cases-->0){		

		scanf("\n");
		scanf("%lf %lf",&B,&H);
		
		r=B/2*tan( 0.5 * atan( 2.0 * H / B ) );
		for(total=0;r>=0.000001;r=B/2*tan( 0.5 * atan( 2.0 * H / B ) )){
			total+=2*pi*r;
			H=H-2*r;
			B=( H/(H+2*r) ) * B ;
		}

		if(nl)
			putchar('\n');
		else 
			nl=1;
		printf("      %.6lf\n",total);	

	}

	return 0;
}

[supermin]

The following is my code.I got P.E.
If you got W.A.,you may check it with my code.

However,could anyone tell me about the standard I/O form.
Why I got P.E.

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double r,total;
	double H,B;
	int cases;
	double pi=2.0*acos(0.0);
	int nl=0;

	scanf("%d",&cases);

	while(cases-->0){		

		scanf("\n");
		scanf("%lf %lf",&B,&H);
		
		r=B/2*tan( 0.5 * atan( 2.0 * H / B ) );
		for(total=0;r>=0.000001;r=B/2*tan( 0.5 * atan( 2.0 * H / B ) )){
			total+=2*pi*r;
			H=H-2*r;
			B=( H/(H+2*r) ) * B ;
		}

		if(nl)
			putchar('\n');
		else 
			nl=1;
		printf("      %.6lf\n",total);	

	}

	return 0;
}

[newtype feng]

try this output

[cpp]printf("%13.6lf\n",res);[/cpp]

[Abednego]

What was your mistake? I think that the answer should be 0.827656, so mine is probably similar to yours.

[sohel]

- one type of mistake could arise is by not considering the input order properly. The fact that both B and H are equal could lead to some error..
.. ie first number is B, then H follows.

but this problem has really got some error...
.. you have to follow the technique that was used by the judges solution, otherwise sample won't match. Any other approach( though correct ) will not be ACed over here.

AFAIR, I got something like 0.827656 for the sample, then with a different approach managed to get the sample right -- and got AC.

[Abednego]

Looks like this is another problem that needs to be fixed. A closed-form solutions is clearly better than a partial sum of a series.

[dumb dan]

Actually it isn't wrong, it clearly states:

you may limit the radius of the smallest inscribed circle in the stack to a single precision floating point value of 0.000001

That is, they aren't looking for the total sum, but rather the total sum not counting any circles with radius smaller than 0.000001. Otherwise the answer would simply be pi*H.

[Abednego]

Ok. So the correct order of doing this is:
1. Compute the largest radius and the factor by which the triangle gets reduced.
2. Sum up all the radii larger than or equal to 0.000001.
3. Print out 2*PI times the total radius sum.
Use double, not float.