11102 - Moonshine

Artikali · Post by **Artikali** » Thu Oct 05, 2006 4:36 am

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

#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 · Post by **gvcormac** » Thu Oct 05, 2006 11:03 am

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 · Post by **Artikali** » Thu Oct 05, 2006 4:55 pm

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 · Post by **gvcormac** » Thu Oct 05, 2006 5:26 pm

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 · Post by **sclo** » Thu Oct 05, 2006 9:25 pm

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 · Post by **Artikali** » Fri Oct 06, 2006 4:51 pm

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 · Post by **gvcormac** » Sat Oct 07, 2006 3:10 am

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 · Post by **marco_dick** » Sun Nov 26, 2006 7:59 am

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 · Post by **jichen1234** » Tue Mar 20, 2007 11:04 am

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 · Post by **Erik** » Fri Apr 06, 2007 2:22 pm

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

Cu, Erik

jichen1234 · Post by **jichen1234** » Mon Apr 09, 2007 7:38 am

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

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 · Post by **Erik** » Mon Apr 09, 2007 8:53 am

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 · Post by **Erik** » Mon Apr 09, 2007 9:21 am

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 · Post by **jichen1234** » Mon Apr 09, 2007 11:25 am

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

Erik · Post by **Erik** » Mon Apr 09, 2007 11:34 am

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

OJ Board

11102 - Moonshine

11102 - Moonshine

Re: 11102 Moonshine WA

Re: 11102 Moonshine

To Erik