Page 1 of 2

10320 - Cow Trouble! Help Please!!

Posted: Wed Jul 03, 2002 1:45 pm
by Dominik Michniewski
I try to solve this problem ... but without success. ...
I have one question: Is any mathematical formula to solve this problem ? I will be greatful for reply :-)

Posted: Wed Jul 03, 2002 2:22 pm
by Picard
there are some different cases depending of the input. when R<l+r it's kinda easy. for R>l+r you can still use a mathematical formula based on pie (a circle wedge) and triangle area calculations.

unfortunatelly the sample input has only R<l+r. here is few other samples:
input:

Code: Select all

1 2 3
1 2 4
3 3 9
2 8 20
5 10 20
output:

Code: Select all

25.1327412287
47.0207005142
239.5411849483
1227.2996538964
1175.5175128556

Posted: Wed Jul 03, 2002 4:01 pm
by Dominik Michniewski
Thanks Picard .... I try to solve this problem at night :-) My mistake was try to find one formula for all cases ...
Thanks too for input & output data :D

Posted: Wed Jul 03, 2002 4:11 pm
by 10153EN
Dear Picard,

Just for my curiosity and personal opinion, as you usually reply the message by stating that you have taken a look at the judge's input (I don't know how do you do so, and it's not what I feel curious and interesting in), I wonder is it the correct direction to solve the problems of ACM?

If I know the input data, then what I do is just to debug for the program for the input data that gives me the WA is not so difficult, and that solving the problems becomes a trial-and-error procedure. Then does solving the problems still meaningful?

Just my personal comment, if you feel my words are offending, sorry about that~ :roll:

Posted: Wed Jul 03, 2002 5:09 pm
by Picard
i never know the judge's input. for example in this case i was talking about the sample input in the problem description. in other cases i send in a test program (or someone's program posted to the board) to test if the input is really in the format as the program expects. example P168, which has probably wrong input data. ofcoz i'am not sure, and i always try to solve first the problem without the plus information sent back from the program. example i can signal back with abort()

if you don't like when someone posts sample input/outputs other than the one in the problem description, it's a different problem. ofcoz this still can spoil a problem, but not for all. there is always a big interest for tricky inputs.

btw there is a contest on which the input is public and you have to send only the output. ofcoz these problems are much harder.
http://ipsc.ksp.sk/

Sorry about that~

Posted: Wed Jul 03, 2002 6:02 pm
by 10153EN
Dear Picard,

Sorry for my words before. The reason behind my words is probably my poor English. When I checked the board, I have seen some message you posted has something like "I checked the judge's input ...* and my poor English thinks that you had a look on the judge's input data and found that... That's my misunderstanding, sorry about that~ :wink:

Posted: Wed Jul 03, 2002 6:14 pm
by Revenger
To Picard:
I just wonder how your program can work only 0.060 seconds! My program work 0.190 seconds. May be you have a very very good formula or C++ is much faster than PASCAL ... :wink:

Posted: Wed Jul 03, 2002 6:14 pm
by Picard
you are right, i will be carefully about how i write it next time and always point out that i can only check if some presumption if true or false for the judge's input ( everybody can do it too with abort(), or more complicated memory allocation or time delay stuff )

Posted: Wed Jul 03, 2002 6:21 pm
by Picard
my first version (which was accepted in the compo, with standard i/o scanf,printf ) was 0.180sec. i still use the same formula (only eliminated one or two sqrt), only the I/O float reading and writing is fully manual.

Posted: Wed Jul 03, 2002 6:39 pm
by Revenger
Wow! It's great that you have done. But in PASCAL i can not do the same :(

Posted: Thu Jul 04, 2002 1:18 pm
by Adrian Kuegel
What is the output of:
3000 3000 9000
I get 239541184.9483201802, but I have perhaps some precision errors.

Posted: Thu Jul 04, 2002 1:25 pm
by Ivan Golubev
My accepted program also outputs 239541184.9483201802 (if compiled with GCC, when compiled with WatcomC results differs in ~1e-5).

Don't worry about precision errors

Posted: Thu Jul 04, 2002 2:00 pm
by shahriar_manzoor
You don't have to worry about precision erros because it is 1e-7 for single unit. So if judge outpur is 1000000000 then your output can vary with it by less than 1000000000*1e-7. So if you are still getting precision errors then you have made a mistake :-)

Posted: Thu Jul 04, 2002 2:05 pm
by Adrian Kuegel
Thanks, now I got Accepted. It was an error in the if statement, which calculation should be made.

Posted: Fri Jul 05, 2002 5:57 pm
by Joe Smith
Does anyone see anything obviously wrong with this, or do you think it's floating point fuzz? I'm getting WA, but all the test cases I've tried including the ones posted here come out correct to all 10 decimal places.

[cpp]

#define M_PI 2.0*acos(0)

int main()
{
double l, w, R, x, y, a, b, c, d;
while (scanf("%lf %lf %lf", &l, &w, &R)==3) {
if (l==0 || w==0)
printf("%0.10lf\n", M_PI*R*R);
else if (l>=R && w>=R)
printf("%0.10lf\n", 0.75*M_PI*R*R);
else if (l>=R)
printf("%0.10lf\n", 0.75*M_PI*R*R + 0.25*M_PI*(R-w)*(R-w));
else if (w>=R)
printf("%0.10lf\n", 0.75*M_PI*R*R + 0.25*M_PI*(R-l)*(R-l));
else if (l+w>=R)
printf("%0.10lf\n", 0.75*M_PI*R*R +
0.25*M_PI*(R-w)*(R-w) +
0.25*M_PI*(R-l)*(R-l));
else {
a = l*l + w*w;
b = 2.0*l*(l-w)*R + 2.0*l*w*w;
c = (l-w)*(l-w)*R*R - w*w*R*R + w*w*2.0*R*l;
d = b*b-4.0*a*c;

assert(d >= 0);
y = 0.5/a*(-b-sqrt(d));
x = -sqrt(R*R - 2.0*R*l - 2.0*y*l - y*y);
a = 0.75*R*R + 0.25*((R-w)*(R-w) + (R-l)*(R-l));
a *= M_PI;
double t = asin(y/(R-w));
double s = asin(-1.0);
a -= 0.5*(R-w)*(R-w)*(t+y/(R-w)*cos(t) - s+cos(s));
t = asin((-y-l)/(R-l));
a -= 0.5*(R-l)*(R-l)*(t+(-y-l)/(R-l)*cos(t));
a += w*(-y-l);

printf("%0.10lf\n", a);
}
}
}
[/cpp]
[/cpp]