Page 1 of 2
11373 - Happy Birthday
Posted: Sat Dec 29, 2007 6:45 pm
by Monsoon
Could anyone give some i/o ?
EDIT:
verify?
Code: Select all
100 100
1 1 0 1
10 2 -2 -20
100 45
-100 -1 100 2
3 100 -4 -100
100 65
24 -43 24 -44
-45 78 -46 78
Code: Select all
1046872.19 524243.69
648388.69 65709.36
962958.92 58058.69
EDIT':
correct one, after finding very stupid bug...
Code: Select all
1100617.88 450178.78
369184.75 342170.82
1236079.49 28298.12
Try this test case
Posted: Sun Dec 30, 2007 1:23 pm
by mitsiddharth
The correct output must be :
But it seems as if there is no such test case in the judge's test cases.
ie , The area of the largest piece is never greater than half the area of the cake in any of judge's input. I thk these cases can also be included.
Please correct me if i am wrong.
Posted: Sun Dec 30, 2007 1:29 pm
by Observer
I think I have included this kind of cases...
Can anyone verify that?
Posted: Sun Dec 30, 2007 1:31 pm
by mitsiddharth
No , i dont thk u have !
I didnt handle such cases in contest time , and managed to get AC !!
Do u understand the kind of test cases i m trying to say??
Posted: Sun Dec 30, 2007 1:32 pm
by mitsiddharth
And ... can u pls post the judge solutions for the above test cases if u dont mind ?
Posted: Sun Dec 30, 2007 1:35 pm
by Observer
Yes I understand what you mean.
But I look at the input file that I sent and there really are cases where size of larger piece > half of size of cake... And to solve such cases, one doesn't even need to treat them specially.
Of course, I don't know if the test data they use have been modified or not.
Posted: Sun Dec 30, 2007 1:41 pm
by mitsiddharth
Are u sure ??
Because , my AC code gives o/p for the following test case :
as
which is wrong ... Thats y i asked ...
Please verify . The only way i cud have got away with that is when there is no such test case !!
Posted: Sun Dec 30, 2007 1:43 pm
by Observer
Well I get "277.68 2.40"...
I don't know, but you can write a mail to the admins of the online judge, and ask them to add test cases like yours.
P.S. I guess I have a case like this:
Maybe your wrong code is clever enough to compute the correct result for this case!
Posted: Sun Dec 30, 2007 2:04 pm
by Observer
Oh I see that (0, 9) is inside the circle (cake). Is that the reason why your program gives incorrect result?
Posted: Sun Dec 30, 2007 2:05 pm
by mitsiddharth
Yes, my wrong code gets away with this !!
But fails, when the larger piece is "really" large .. maybe becos of my logic to solve the problem.
Posted: Thu Jan 03, 2008 5:49 am
by andmej
I can't solve this problem.
Any advice? How should start? I only want a subtle clue.
Thanks!
Posted: Thu Jan 03, 2008 7:05 am
by Observer
If you have absolutely no idea where to start, try drawing some cases on paper. I think you should at least know how to compute the areas on paper......
Posted: Thu Jan 03, 2008 9:19 am
by andmej
I tried that and have thought a lot.
However I can't see a solution using basic geometry. I tried with integral calculus but got stock. Is there a solution using Euclidian or Analytic Geometry?
Posted: Thu Jan 03, 2008 12:59 pm
by Darko
As suggested, draw a picture, and then mark everything that you know and see if you can get what you want to know from that.
Hint: look at the triangles.
Posted: Thu Jan 03, 2008 2:03 pm
by Observer
If you fail to get anything from your drawings then I don't know what hints I can give, since it seems that you don't even know what you are trying to compute... I think you should at least try to work out mitsiddharth's sample by hand (and calculator). Otherwise I am afraid that no hint will be useful to you.