10320 - Cow Trouble! Help Please!!

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10320 - Cow Trouble! Help Please!!

Post 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 :-)

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post 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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post 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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post 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:

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post 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/

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Sorry about that~

Post 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:

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post 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:

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post 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 )

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

Wow! It's great that you have done. But in PASCAL i can not do the same :(

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

What is the output of:
3000 3000 9000
I get 239541184.9483201802, but I have perhaps some precision errors.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

My accepted program also outputs 239541184.9483201802 (if compiled with GCC, when compiled with WatcomC results differs in ~1e-5).

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Don't worry about precision errors

Post 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 :-)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Thanks, now I got Accepted. It was an error in the if statement, which calculation should be made.

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post 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]

Post Reply

Return to “Volume 103 (10300-10399)”