375 - Inscribed Circles and Isosceles Triangles

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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?

Post by AlexandreN » Tue Aug 27, 2002 7:30 pm

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

Post by Mahbub » Fri Sep 27, 2002 7:49 am

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

Post by SMBfromRU » Fri Nov 22, 2002 1:32 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

375 - Inscribed Circles and Isosceles Triangles

Post by little joey » Tue Mar 11, 2003 12:20 pm

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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Fri Apr 18, 2003 11:20 am

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:

Post by supermin » Thu May 01, 2003 6:39 pm

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:

Post by supermin » Thu May 01, 2003 6:41 pm

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:

Post by supermin » Thu May 01, 2003 6:44 pm

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:

Post by supermin » Thu May 01, 2003 6:46 pm

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

Post by newtype feng » Thu Jul 31, 2003 2:47 pm

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed May 04, 2005 3:03 am

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...

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

Post by sohel » Wed May 04, 2005 2:55 pm

- 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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed May 04, 2005 10:02 pm

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...

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu May 05, 2005 4:29 pm

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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu May 05, 2005 5:23 pm

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...

Post Reply

Return to “Volume 3 (300-399)”