Sunday, December 12, 2010

UVA - 10167 - Birthday Cake

problem statement

computational geometry, brute force, complete search

In this problem You have a cake with radius 100 and 2N cherries that are placed on the cake.
The center of the cake is Origin, You have to cut the cake in 2 parts in a fairly manner that each part has equal cherries and no cherry is on the beeline of division.
Since There are at most 100 cherries and the beeline must go through the center of the cake and the radius of the cake is 100, You can set (A >= 0 && A <= 100) and (B >= -100 && B <= 100) and each time make a beeline with this A and B (Ax+By=0) that goes through the Origin and check whether there are equal cherries
in each side of the beeline and no cherry is on the beeline, if yes print x and y and break.
Check if( A*x[i]+B*y[i] > 0 ) one ++; else if( A*x[i]+B*y[i] < 0 ) two ++;
if( one == n && two == n ) print A and B.
In this way you will get an accept in the suggested time limit.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...