11373 - Happy Birthday

[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

[mitsiddharth]

Code: Select all

10 1
0 9 10 9
0 9 10 0

The correct output must be :

Code: Select all

277.68 2.40

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.

[Observer]

I think I have included this kind of cases...

Can anyone verify that?

[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??

[mitsiddharth]

And ... can u pls post the judge solutions for the above test cases if u dont mind ?

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

[mitsiddharth]

Are u sure ??
Because , my AC code gives o/p for the following test case :

Code: Select all

10 1
0 9 10 9
0 9 10 0 

as

Code: Select all

75.71 2.40

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 !!

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

Code: Select all

2 1
-10 -1 10 -1
-1 -10 -1 10

Maybe your wrong code is clever enough to compute the correct result for this case!

[Observer]

Oh I see that (0, 9) is inside the circle (cake). Is that the reason why your program gives incorrect result?

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

[andmej]

I can't solve this problem.

Any advice? How should start? I only want a subtle clue.

Thanks!

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

[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?

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

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