11257 - New Marketing Plan

[sclo]

I keep getting WA for this problem. I'm not quite sure about my approach.

Basically, for any circle with the maximum radius, the circle must touch exactly 3 sides of the polygon. So I just iterate through every 3 sides of the polygon.

I consider the 3 sides as lines, and compute 2 intersections A,B. 2 intersections must exist since at most 2 of the sides can be parallel. The center of the circle will be the intersection of the angle bisectors of A,B.
Then I check whether the computed circle with that radius actually is valid, meaning it lies within the polygon.

I don't see anything wrong with this approach.

[ayon]

i did same as sclo using O(n^4), but i got TLE. there must have some better approaches

[mf]

There's O(n log n) solution - imagine that the sides of the polygon are moving towards its inside, each side moves along its perpendicular direction at unit speed (like in this picture). Basically, the time it takes to shrink the whole polygon to a point is the maximum radius of inscribed circle. You could simulate this process with a binary heap (to quickly find which side disappears next) to get O(n log n) time.

(Of course, with n<=50 heap is completely unnecessary, but it's needed for this problem - http://acm.sgu.ru/problem.php?contest=0&problem=332 )

[Ivan]

What I did is a nested ternary search - the outer one over the x, and the
inner one over y for every x in the outer search. X and y are the coordinates
of the center of the circle.
In the contest it took a few submissions to figure out the right balance
between precision and runtime but finally I got "solved". I had in mind
sclo's approach but had the feeling that its complexity is even worse.
The O(n logn) aprroach suggested by mf sounds very interesting, but
honestly speaking I do not quite get it...

[sclo]

mf's shrinking idea is a good one. It's like working backwards.

[sunny]

EDITED

[mf]

(as the circle should always touch at least 1 pair of adjacent edge).

Why adjacent?
I think you'll need to check all pairs of edges.

[sunny]

oops...you are right.
sorry for posting a foolish algorithm.

[sonyckson]

Hello... im thincking a O( n^3*log) solution ... but of course this complexity wouldnt be enough for mf's posted problem.. so i wanted to ask you mf if you could tell us a little more about your idea...
Another question... is there any algorithm that can tell as if a point is inside a convex polygon in O(1)? thanks!. eric

[mf]

For each polygon's side compute the time at which it will disappear due to its neighbors' motion. Maintain the set of currently visible sides in a min-heap, and repeatedly choose the side which must disappear next, remove it, update its neighbors' disappearing times, and so on. Repeat until the polygon has shrunk into a point or a line segment.

AFAIK some people got away with nested ternary search, so you might want to try it as well.

is there any algorithm that can tell as if a point is inside a convex polygon in O(1)?

O(n) preprocessing, O(log n) per query: choose some point M strictly inside the polygon (average of vertices' coordinates works fine), sort the polygon's vertices around it by angle. For a query point Q, use binary search to find two adjacent vertices A, B, such that Q lies between rays MA and MB, and check whether Q is also in the triangle MAB.

[sclo]

The result of my own algorithm is correct, the WA comes from the fact that my function for computing angle bisector is bugged. I can't believe that I fixed so many other stuff that I didn't see it.

for example:
angle a+b == a+b+2pi but (a+b)/2 != (a+b+2pi)/2

[cpphamza]

In the contest it took a few submissions to figure out the right balance between precision and runtime but finally I got "solved".

I've implemented this approach using epsilon=0.0009 but got WA, can you tell me the largest value of epsilon you used to get it solved?

[sclo]

In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6.

More about my method: I treated the case there're 2 adjacent sides parallel as special cases. The sample input doesn't have that case. It is possible that 2 adjacent sides are parallel if we keep removing sides. Also, if we use the O(n^4) algorithm of choosing every 3 sides, this case would also appear.

[cpphamza]

In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6.

The thing is that this is the smallest epsilon I can use without timeouting, I wonder if people that solved it using the nested ternary search approach did something better in complexity than the following:
1-Ternary search on values of x
2- For each value of x from above ternary search on values of y
3- For a pair of x,y check if the point is inside the polygon in O(n) and if inside return the minimum distance from x,y to any line of the polygon in O(n) too where n is the number of points (max 50)

Any help is appreciated.

[baodog]

You can give golden section search a try.
if evaluating f takes most of the time per iteration
, it's faster than ternary.

http://en.wikipedia.org/wiki/Golden_section_search