11257 - New Marketing Plan

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11257 - New Marketing Plan

Post by 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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

i did same as sclo using O(n^4), but i got TLE. there must have some better approaches
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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 )
Last edited by mf on Sun Aug 05, 2007 12:03 am, edited 2 times in total.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

EDITED
Last edited by sunny on Sat Aug 04, 2007 10:09 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

sunny wrote:(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
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

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

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by cpphamza »

Ivan wrote: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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by cpphamza »

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.
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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Golden Section Search

Post by 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

Post Reply

Return to “Volume 112 (11200-11299)”