11102 - Moonshine

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

Moderator: Board moderators

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

11102 - Moonshine

Post by Artikali »

Please help me, i tested it with several test case, but it was WA
here is my code

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
using namespace std;
const double err=0.001;
const double  pi=acos(-1.0);
double S(double r,double t){
	double a=2*acos((r-t)/r);
	double s=0.5*r*r*(a-sin(a));
	return s;
}
double VCyl(double R,double h,double t){
	double ret;
	ret=S(R,t)*h;
	return ret;
}
double VCone(double R,double h,double t){
	double ret,h1;
	if (R>=t)
	{
		h1=t*h/R;
		ret=S(R,t)*h1/3.0;
	}
	else
	{
		t=2*R-t;
		h1=t*h/R;
		double s=S(R,t);
		ret=pi*R*R*h/3.0-s*h1/3.0;
	}
	return ret;
}
double VConehalf(double R,double r,double h, double t){
	double h1=(r*h)/(R-r);//kichik konusning balndligi, h esa orasidagi balandlik
	double Vkichik;
	double Vkatta=VCone(R,h1+h,t);
	if (t<(R-r)) Vkichik=0.0;
	else if (t<(R+r))
		Vkichik=VCone(r,h1,t+r-R);
	else Vkichik=pi*r*r*h1/3.0;
	double ret=Vkatta-Vkichik;
	return ret;
}
double Volume(double R,double r,double h1, double h2,double h3,double t){
	double vcyl_katta=VCyl(R,h1,t);
	double vcon=VConehalf(R,r,h2,t);
	double vcyl_kichik;
	if (t<(R-r)) vcyl_kichik=0.0;
	else if (t<(R+r))
		vcyl_kichik=VCyl(r,h3,t+r-R);
	else vcyl_kichik=pi*r*r*h3;
	double ret=vcyl_katta+vcon+vcyl_kichik;
	return ret;
}
double bisearch(double R,double r,double h1,double h2,double h3,
			 double V,double left,double right){
	 double mid=(left+right)/2.0,ret;
	 if (fabs(right-left)<0.01) 
		 return mid;
	 double Vol=Volume(R,r,h1,h2,h3,mid);
	 if (fabs(V-Vol)<err) return mid;
	 if (V<Vol){
		 ret=bisearch(R,r,h1,h2,h3,V,left,mid);
	 }
	 else 
	 {
		 ret=bisearch(R,r,h1,h2,h3,V,mid,right);
	 }
	 return ret;
}
 double allV;
int main(){
	freopen("a.in","r",stdin);
	double k,hb,db,hn,dn,h;
	//k=3.592;	printf("%.2f\n\n",k);
	double H,h1,h2,h3,R,r,V,a,b,r1;
	while(1){
		cin>>k>>hb>>db>>hn>>dn>>h;
		if (int(k+hb+db+hb+dn+h)==0) break;
		H=h; h1=hb; h3=hn; h2=H-h1-h3;
		R=db/2.0; r=dn/2.0; r1=(h1+h2-k)*R/h2;
		if (k<=h1) V=pi*R*R*k;
		else if (k<=h1+h2) V=pi*R*R*h1+pi*(k-h1)*(R*R+R*r1+r1*r1)/3;
		else V=pi*R*R*h1+pi*h2*(R*R+R*r+r*r)/3.0+pi*r*r*(k-h1-h2);
		allV=pi*R*R*h1+pi*h2*(R*R+R*r+r*r)/3.0+pi*r*r*h3;
		double t=bisearch(R,r,h1,h2,h3,V,0.0,2*R);
		assert(((int)t)!=-1);
		printf("%.2f\n",t);
	}
	return 0;
}
thanks

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Re: 11102 Moonshine WA

Post by gvcormac »

Artikali wrote:Please help me, i tested it with several test case, but it was WA
here is my code

thanks
Not sure what you are doing but I don't see any code that integrates to find the volume of a cone sliced by a plane parallel to its axis. This integral is nasty. Dr. Math has an incorrect solution and I have not been able to find a correct closed solution on the web. Except, I suppose, for the Waterloo site which gives a closed solution and also two numerical solutions.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali »

integral is nasty, but it has a simple solution to find the volume of a cone sliced by a plane parallel to its axis. First you to find of area of the base of a cone(segment of the base circle) and multiply to height(not height of con) and devide it 3
R - radius of a cone
h - height of a cone
t,p - slices (t+p=R)
cos(a/2)=(R-t)/R;
a=2*acos((R-t)/R);
area Segment of the base S=1/2*R*R(a-sin(a));
heigt of the slice is h1=t*h/R;
Volume of the slice is V=1/3*S*h1;
i proved it.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

Artikali wrote:integral is nasty, but it has a simple solution to find the volume of a cone sliced by a plane parallel to its axis. First you to find of area of the base of a cone(segment of the base circle) and multiply to height(not height of con) and devide it 3
R - radius of a cone
h - height of a cone
t,p - slices (t+p=R)
cos(a/2)=(R-t)/R;
a=2*acos((R-t)/R);
area Segment of the base S=1/2*R*R(a-sin(a));
heigt of the slice is h1=t*h/R;
Volume of the slice is V=1/3*S*h1;
i proved it.
I don't think that's right. It assumes the shape of the cross-section
is invariant. It isn't.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I've found that approximating the integral by piecewise constant functions (ie. midpoint) give WA, but approximating the integral by piecewise quadratics (ie. Simpson's) gives AC. I couldn't find any ways to symbolically integrate the integral that is nice. I tried it on Maple but it returns pages of output.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali »

if R>t then it would be right.else { t=R-t; V=Volume cone -Volume Slice;}
let's prove it.
if (R>t)
[img=http://img322.imageshack.us/img322/7932 ... sr4.th.jpg]
[/url]

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

Artikali wrote:if R>t then it would be right.else { t=R-t; V=Volume cone -Volume Slice;}
let's prove it.
if (R>t)
[img=http://img322.imageshack.us/img322/7932 ... sr4.th.jpg]
[/url]
The shape is not a pyramid, and the formula doesn't apply. The formula assumes that the cross-sectional area d vertical units from the top is equal to kd^2 for some k. Then it integrates d from 0 to h giving giving 1/3kh^3 or 1/3h(kh^2); that is 1/3 height times base area. But the assumption that the cross-sectional area is kd^2 is incorrect, because cross-sections at different heights are not similar (in the geometric sense) so the area is not proportional to the square of some linear dimension. Near the base the cross section is more nearly a semi-disk than near the top, where it becomes just a thin sliver.

marco_dick
New poster
Posts: 2
Joined: Tue Aug 01, 2006 6:34 am

Post by marco_dick »

I have written this program, and tried several test cases to get correct answer. But when I submitted, I got WA. So may anyone who have got AC give me some test cases (just a few is okay) for me to check? Thanks.

jichen1234
New poster
Posts: 8
Joined: Fri May 20, 2005 5:53 pm

Re: 11102 Moonshine

Post by jichen1234 »

Artikali wrote:Please help me, i tested it with several test case, but it was WA
here is my code
thanks
Hi, try

Input
15 0 10 0 0 15

Output should be 10.00
but ur program's ouput is 9.98

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik »

Hi,

could anyone provide me outpus of the following testcases:

Code: Select all

0 10 20 5 5 25
1 10 20 5 5 25
2 10 20 5 5 25
3 10 20 5 5 25
4 10 20 5 5 25
5 10 20 5 5 25
6 10 20 5 5 25
7 10 20 5 5 25
8 10 20 5 5 25
9 10 20 5 5 25
10 10 20 5 5 25
11 10 20 5 5 25
12 10 20 5 5 25
13 10 20 5 5 25
14 10 20 5 5 25
15 10 20 5 5 25
16 10 20 5 5 25
17 10 20 5 5 25
18 10 20 5 5 25
19 10 20 5 5 25
20 10 20 5 5 25
21 10 20 5 5 25
22 10 20 5 5 25
23 10 20 5 5 25
24 10 20 5 5 25
25 10 20 5 5 25
0 0 0 0 0 0
My outputs are:

Code: Select all

0.00
2.85
4.41
5.69
6.82
7.85
8.79
9.69
10.59
11.50
12.46
13.44
14.35
15.17
15.92
16.59
17.18
17.69
18.11
18.43
18.65
18.83
19.03
19.26
19.53
20.00
Cu, Erik :)

jichen1234
New poster
Posts: 8
Joined: Fri May 20, 2005 5:53 pm

To Erik

Post by jichen1234 »

To Erik:

I also got WA. While compared to your testcase, all are different except the first and the last testcase.
The following outputs are generated by my WA prog.

Code: Select all

0.00
2.43
3.92
5.22
6.42
7.56
8.62
9.65
10.67
11.70
12.79
13.86
14.81
15.66
16.40
17.05
17.60
18.06
18.43
18.71
18.90
19.05
19.22
19.40
19.63
20.00
Can u try the following testcase

Code: Select all

7.344 10 20 5 5 25
0 0 0 0 0 0
My output is

Code: Select all

10.00
I think the volumun of the above case is 2307.185645, which is approximately half of the total volumn of the bottle.
Total volumn of the bottle is 4614.214210
Can u help me verify my results? Thx

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik »

Hi jichen1234,

my prog says 10.00 to your testcase.
I will now try to find results with an algebra system to verify our outputs.

Cu, Erik :)

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik »

Hi again,

for test case

Code: Select all

1 10 20 5 5 25
The volume is about 314.1592654.
If I didn't mess it up my calculator tells me the volume for s=2.85 is 314.6619124 and for s=2.43 the volume is 244.8805116.

Am I wrong?
I used the following formula to calculate the area of fluid at a cross section where the current radius of the bottle is r and x is the distance from the water surface to the middle of the circle (e.g. x=rb-s):

Code: Select all

A = r^2*arccos(x/r) - x*sqrt(r^2-x^2)
After integration I got the values above.

Could you verify this?

Cu, Erik :)

jichen1234
New poster
Posts: 8
Joined: Fri May 20, 2005 5:53 pm

Post by jichen1234 »

We use the same idea calculating the cross section.

In fact, I directly calculate the volume of the cross section instead of integration.

Code: Select all

V= fan-based pyramid - triangular-based pyramid
 = (1/3)*h*[r*r*acos(x/r)] - (1/3)*h*x*[sqrt(r*r-x*x)]
But I'm not sure whether the calculation of triangular-based pyramid is correct. I also tried 1/6 instead of 1/3, but still got WA.

ref. http://www.nrich.maths.org/public/viewe ... hindex.php
http://argyll.epsb.ca/jreed/math9/strand3/3106.htm
Last edited by jichen1234 on Mon Apr 09, 2007 11:38 am, edited 1 time in total.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik »

Hi,

I can't follow your equation:

Code: Select all

V= 1/3[r*r*acos(x/r)] - 1/3[ sqrt(r*r-x*x)]*x
If you consider the cylindric parts of the bottle, it's true that the cross section is constant so you can get the volume with

Code: Select all

V = [r^2*arccos(x/r) - x*sqrt(r^2-x^2)] * h
with h being the height of the part.
But the connection of the two cylinders is different. The cross section varies and you have to integrate. The symbolic integral isn't as simple as your equation.

Cu, Erik :)

Post Reply

Return to “Volume 111 (11100-11199)”