Page 1 of 2

11102 - Moonshine

Posted: Thu Oct 05, 2006 4:36 am
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

Re: 11102 Moonshine WA

Posted: Thu Oct 05, 2006 11:03 am
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.

Posted: Thu Oct 05, 2006 4:55 pm
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.

Posted: Thu Oct 05, 2006 5:26 pm
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.

Posted: Thu Oct 05, 2006 9:25 pm
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.

Posted: Fri Oct 06, 2006 4:51 pm
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]

Posted: Sat Oct 07, 2006 3:10 am
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.

Posted: Sun Nov 26, 2006 7:59 am
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.

Re: 11102 Moonshine

Posted: Tue Mar 20, 2007 11:04 am
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

Posted: Fri Apr 06, 2007 2:22 pm
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 :)

To Erik

Posted: Mon Apr 09, 2007 7:38 am
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

Posted: Mon Apr 09, 2007 8:53 am
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 :)

Posted: Mon Apr 09, 2007 9:21 am
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 :)

Posted: Mon Apr 09, 2007 11:25 am
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

Posted: Mon Apr 09, 2007 11:34 am
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 :)