## 375 - Inscribed Circles and Isosceles Triangles

Moderator: Board moderators

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

### Problem 375 - What's the problem?

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
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

### 375 ..WA

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
New poster
Posts: 7
Joined: Wed Sep 11, 2002 9:19 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 375 - Inscribed Circles and Isosceles Triangles

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;
for caseno:=1 to cases do begin
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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
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
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

### i know why you got P.E

try this output [cpp]printf("%13.6lf\n",res);[/cpp]
I like AC

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
What was your mistake? I think that the answer should be 0.827656, so mine is probably similar to yours.
If only I had as much free time as I did in college...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
- 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...