## 11257 - New Marketing Plan

**Moderator:** Board moderators

### 11257 - New Marketing Plan

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.

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.

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 )

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

Last edited by mf on Sun Aug 05, 2007 12:03 am, edited 2 times in total.

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

Another question... is there any algorithm that can tell as if a point is inside a convex polygon in O(1)? thanks!. eric

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

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.is there any algorithm that can tell as if a point is inside a convex polygon in O(1)?

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.

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:sclo wrote: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.

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.

### Golden Section Search

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

if evaluating f takes most of the time per iteration

, it's faster than ternary.

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